Hell, P.; Kirkpatrick, D. G. Packings by complete bipartite graphs. (English) Zbl 0597.05050 SIAM J. Algebraic Discrete Methods 7, 199-209 (1986). Summary: Given any set \({\mathcal B}\) of complete bipartite graphs, we ask whether a graph H admits a \({\mathcal B}\)-factor, i.e., a spanning subgraph, each of whose components is a member of \({\mathcal B}\). More generally, we seek in H a maximum \({\mathcal B}\)-packing, i.e., a \({\mathcal B}\)-factor of a maximum size subgraph of H. We first treat the interesting special case when \({\mathcal B}\) is a set of stars. The results are generalized to arbitrary \({\mathcal B}\) in the last section. We prove for most of these problems that they are \({\mathcal N}{\mathcal P}\)-hard; we also show that the remaining problems admit polynomial algorithms based on augmenting configurations. The simplicity of these algorithms, as well as the implied min-max theorems, resemble the theory of matchings in bipartite, rather than general, graphs. Cited in 1 ReviewCited in 27 Documents MSC: 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 68R10 Graph theory (including graph drawing) in computer science Keywords:complete bipartite graphs; \({\mathcal B}\)-packing; \({\mathcal B}\)-factor PDFBibTeX XMLCite \textit{P. Hell} and \textit{D. G. Kirkpatrick}, SIAM J. Algebraic Discrete Methods 7, 199--209 (1986; Zbl 0597.05050) Full Text: DOI References: [1] Akiyama, Jin; Kano, Mikio, Path factors of a graph, Graphs and applications (Boulder, Colo., 1982), 1, (1985), Wiley, New York · Zbl 0561.05044 [2] Akiyama, Jin; Avis, David; Era, Hiroshi, On a \(\{1,\,2\}\)-factor of a graph, TRU Math., 16, 97, (1980) · Zbl 0461.05047 [3] Amahashi, Atsushi; Kano, Mikio, On factors with given components, Discrete Math., 42, 1, (1982) · Zbl 0525.05048 [4] Belck, H. B., Reguläre faktoren von graphen, J. Reine Angew. Math., 188, 228, (1950) · Zbl 0040.26001 [5] Berge, Claude, Two theorems in graph theory, Proc. Nat. Acad. Sci. U.S.A., 43, 842, (1957) · Zbl 0086.16202 [6] Berge, Claude, Sur le couplage maximum d’un graphe, C. R. Acad. Sci. Paris, 247, 258, (1958) · Zbl 0086.16301 [7] On the existence of subgraphs with degree constraintsProc. Nederl. Akad. Wetensch, (cited in [31]) [8] Cornuejols, Gerard; Pulleyblank, William, A matching problem with side conditions, Discrete Math., 29, 135, (1980) · Zbl 0446.05031 [9] Cornuejols, G.; Hartvigsen, D.; Pulleyblank, W., Packing subgraphs in a graph, Oper. Res. Lett., 1, 139, (198182) · Zbl 0488.90070 [10] Cornuejols, G.; Pulleyblank, W. R., Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem, Combinatorica, 3, 35, (1983) · Zbl 0535.05038 [11] Dinic, E. A., Algorithm for solution of a problem of maximum flow in a network with power estimation, Soviet Math. Dokl., 11, 1277, (1970) · Zbl 0219.90046 [12] Edmonds, Jack, Paths, trees, and flowers, Canad. J. Math., 17, 449, (1965) · Zbl 0132.20903 [13] Edmonds, Jack, Maximum matching and a polyhedron with \(0,1\)-vertices, J. Res. Nat. Bur. Standards Sect. B, 69B, 125, (1965) · Zbl 0141.21802 [14] Edmonds, Jack; Johnson, EllisL.; Guy, R. K., Matching: A well-solved class of integer linear programs, Combinatorial Structures and their Applications (Proc. Calgary Internat., Calgary, Alta., 1969), 89, (1970), Gordon and Breach, New York · Zbl 0258.90032 [15] Erdös, P.; Gallai, T., On the minimum number of vertices representing the edges of a graph, Publ. Math. Inst. Hung. Acad. Sci., 6, 181, (1961) · Zbl 1009.68810 [16] An efficient reduction technique for degree constrained subgraph and bidirected network flow problemsProc. 15th Annual ACM Symposium on Theory of Computing448456 [17] Garey, MichaelR.; Johnson, DavidS., Computers and intractability, (1979) · Zbl 0411.68039 [18] Hajnal, A., A theorem on {\it k}-saturated graphs, Canad. J. Math., 17, 720, (1965) · Zbl 0129.39901 [19] Summer Research Workshop in Combinatorics, Simon Fraser Univ., Aug. 8, 1979; Applied Discrete Math. Seminar, Rutgers Univ., Oct. 23, 1979; 12th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, L.S.U., March 4, 1981; Math. Programming and Combinatorics Seminar, Princeton Univ., Nov. 11, 1981 [20] Hell, P.; Kirkpatrick, D. G., Scheduling, matching, and coloring, Algebraic methods in graph theory, Vol. I, II (Szeged, 1978), 25, 273, (1981), North-Holland, Amsterdam · Zbl 0474.05054 [21] Hell, P.; Kirkpatrick, D. G., On generalized matching problems, Inform. Process. Lett., 12, 33, (1981) · Zbl 0454.68077 [22] Star factors and star packingsTR 82-6Dept. Computing Science, Simon Fraser UniversityBurnaby, British Columbia1982 [23] Hell, P.; Kirkpatrick, D. G., Packings by cliques and by finite families of graphs, Discrete Math., 49, 45, (1984) · Zbl 0582.05046 [24] (g,f)-factorsto appear [25] Hopcroft, JohnE.; Ullman, JeffreyD., Introduction to automata theory, languages, and computation, (1979) · Zbl 0426.68001 [26] Hopcroft, JohnE.; Karp, RichardM., An \(n\sp{5/2}\) algorithm for maximum matchings in bipartite graphs, SIAM J. Comput., 2, 225, (1973) · Zbl 0266.05114 [27] Kameda, Tiko, Testing deadlock-freedom of computer systems, J. Assoc. Comput. Mach., 27, 270, (1980) · Zbl 0431.68032 [28] Kirkpatrick, DavidG.; Hell, Pavol, On the completeness of a generalized matching problem, Conference Record of the Tenth Annual ACM Symposium on Theory of Computing (San Diego, Calif., 1978), 240, (1978), ACM, New York · Zbl 1282.68182 [29] Kirkpatrick, D. G.; Hell, P., On the complexity of general graph factor problems, SIAM J. Comput., 12, 601, (1983) · Zbl 0525.68023 [30] König, D., Graphen and matrizen, Mat. Fiz. Lapok, 38, 116, (1931) · JFM 57.1340.04 [31] Las Vergnas, Michel, An extension of Tutte’s 1-factor theorem, Discrete Math., 23, 241, (1978) · Zbl 0404.05048 [32] Lovász, L., Subgraphs with prescribed valencies, J. Combinatorial Theory, 19B, 269, (1975) · Zbl 0198.29201 [33] An O(|V|⋅|E|) algorithm for finding maximum matching in general graphsProc. 21st Annual Symposium on Foundation of Computer Sciences19801727 [34] Mühlbacher, Jörg, {\it F}-factors of graphs: a generalized matching problem, Inform. Process. Lett., 8, 207, (1979) · Zbl 0426.05043 [35] Shiloach, Yossi, Another look at the degree constrained subgraph problem, Inform. Process. Lett., 12, 89, (1981) · Zbl 0492.05041 [36] Tutte, W. T., The factorization of linear graphs, J. London Math. Soc., 22, 107, (1947) · Zbl 0029.23301 [37] Tutte, W. T., The factors of graphs, Canadian J. Math., 4, 314, (1952) · Zbl 0049.24202 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.