Brewster, Richard C.; Hell, Pavol; Rizzi, Romeo Oriented star packings. (English) Zbl 1139.05027 J. Comb. Theory, Ser. B 98, No. 3, 558-576 (2008). Given a family \(S\) of oriented stars, an \(S\)-packing in a digraph \(D\) is a collection of vertex disjoint subgraphs of \(D\), each of which is isomorphic to a member of \(S\). The \(S\)-packing problem is to ascertain the maximum number of vertices of a host \(D\) that can be covered by an \(S\)-packing of \(D\). The paper shows a dichotomy for the decision version of the \(S\)-packing problem, giving an exact classification of which problems are polynomial time solvable and which are NP-complete. For the polynomial problem, it provides Hall type min-max theorems, including versions for locally degree-constrained variants of the problems. It also shows that the \(S\)-packing problem is polynomial for some \(S\) and NP-complete otherwise. Reviewer: Wai-Kai Chen (Fremont) Cited in 4 Documents MSC: 05C20 Directed graphs (digraphs), tournaments 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) Keywords:oriented star; packing problem; min-max theorem; good characterization PDFBibTeX XMLCite \textit{R. C. Brewster} et al., J. Comb. Theory, Ser. B 98, No. 3, 558--576 (2008; Zbl 1139.05027) Full Text: DOI References: [1] Brewster, R. C.; Hell, P.; Pantel, S. H.; Rizzi, R.; Yeo, A., Packing paths in digraphs, J. Graph Theory, 44, 81-94 (2003) · Zbl 1033.05079 [2] R.C. Brewster, P. Hell, R. Rizzi, Sidepath results on packing \(P_1\)’s and \(P_2\)’s. Technical Report DIT-03-008, Dipartimento di Informatica e Telecomunicazioni, Università degli Studi di Trento, 38050 Trento, Italy; R.C. Brewster, P. Hell, R. Rizzi, Sidepath results on packing \(P_1\)’s and \(P_2\)’s. Technical Report DIT-03-008, Dipartimento di Informatica e Telecomunicazioni, Università degli Studi di Trento, 38050 Trento, Italy [3] Brewster, R. C.; Rizzi, R., Digraph packings with hypomatchable graphs and propellers, Inform. Process. Lett., 86, 101-106 (2003) [4] Cornuéjols, G.; Hartvigsen, D.; Pulleyblank, W., Packing subgraphs in a graph, Oper. Res. Lett., 1, 139-143 (1982) · Zbl 0488.90070 [5] Edmonds, J., Paths, trees, and flowers, Canad. J. Math., 17, 449-467 (1965) · Zbl 0132.20903 [6] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-completeness (1979), Freeman: Freeman San Francisco · Zbl 0411.68039 [7] Hell, P., Graph packings, (Proceedings of the 6ème Colloque International de Théorie des Graphes. Proceedings of the 6ème Colloque International de Théorie des Graphes, Electron. Notes Discrete Math., vol. 5 (2000)) · Zbl 1412.05161 [8] Hell, P.; Kirkpatrick, D. G., On generalized matching problems, Inform. Process. Lett., 12, 33-35 (1981) · Zbl 0454.68077 [9] Hell, P.; Kirkpatrick, D. G., Packings by cliques and by finite families of graphs, Discrete Math., 49, 45-59 (1984) · Zbl 0582.05046 [10] Hell, P.; Kirkpatrick, D. G., Packings by complete bipartite graphs, SIAM J. Algebraic Discrete Methods, 7, 2, 199-209 (1986) · Zbl 0597.05050 [11] Hopcroft, J. E.; Karp, R. M., An \(n^{5 / 2}\) algorithm for maximum matching in bipartite graphs, SIAM J. Comput., 2, 231-255 (1973) · Zbl 0266.05114 [12] Lovász, L.; Plummer, M. D., Matching Theory (1986), North-Holland: North-Holland Amsterdam · Zbl 0618.05001 [13] Loebl, M.; Poljak, S., Efficient subgraph packing, J. Combin. Theory Ser. B, 59, 106-121 (1993) · Zbl 0794.05105 [14] S.H. Pantel, Graph packing problems, MSc Thesis, Simon Fraser University, 1998; S.H. Pantel, Graph packing problems, MSc Thesis, Simon Fraser University, 1998 [15] Rizzi, R., König’s edge colouring theorem without augmenting paths, J. Graph Theory, 29, 2, 87 (1998) · Zbl 0919.05051 [16] Rizzi, R., A short proof of König’s matching theorem, J. Graph Theory, 33, 3, 138-139 (2000) · Zbl 0981.05082 [17] Tarjan, R. E., Data Structures and Network Algorithms (1983), Society for Industrial and Applied Mathematics · Zbl 0584.68077 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.