Combinatorial and computational aspects of graph packing and graph decomposition. (English) Zbl 1302.05149
Summary: Packing and decomposition of combinatorial objects such as graphs, digraphs, and hypergraphs by smaller objects are central problems in combinatorics and combinatorial optimization. Their study combines probabilistic, combinatorial, and algebraic methods. In addition to being among the most fascinating purely combinatorial problems, they are often motivated by algorithmic applications. There is a considerable number of intriguing fundamental problems and results in this area, and the goal of this paper is to survey the state-of-the-art.
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68Q25 | Analysis of algorithms and problem complexity |
| 05C07 | Vertex degrees |
| 05C65 | Hypergraphs |
| 05C80 | Random graphs (graph-theoretic aspects) |
| 05C20 | Directed graphs (digraphs), tournaments |
| 05-02 | Research exposition (monographs, survey articles) pertaining to combinatorics |
References:
| [1] | Alon, N., A note on the decomposition of graphs into isomorphic matchings, Acta Mathematica Academiae Scientiarum Hungaricae, 42, 221-223 (1983) · Zbl 0535.05047 |
| [2] | Alon, N.; Caro, Y.; Yuster, R., Packing and covering dense graphs, Journal of Combinatorial Designs, 6, 451-472 (1998) · Zbl 0914.05013 |
| [3] | Alon, N.; Duke, R. A.; Lefmann, H.; Rödl, V.; Yuster, R., The algorithmic aspects of the Regularity Lemma, Journal of Algorithms, 16, 80-109 (1994) · Zbl 0794.05119 |
| [4] | Alon, N.; Fischer, E., Refining the graph density condition for the existence of almost \(K\)-factors, Ars Combinatoria, 52, 296-308 (1999) · Zbl 0977.05103 |
| [5] | Alon, N.; Spencer, J. H., The Probabilistic Method (2000), Wiley: Wiley New York · Zbl 0996.05001 |
| [6] | Alon, N.; Yuster, R., Threshold functions for \(H\)-factors, Combinatorics, Probability, and Computing, 2, 137-144 (1993) · Zbl 0794.05098 |
| [7] | Alon, N.; Yuster, R., \(H\)-factors in dense graphs, Journal of Combinatorial Theory, Series B, 66, 269-282 (1996) · Zbl 0855.05085 |
| [8] | Arnborg, S.; Lagergren, J.; Seese, D., Easy problems for tree-decomposable graphs, Journal of Algorithms, 12, 308-340 (1991) · Zbl 0734.68073 |
| [9] | B.S. Baker, Approximation algorithms for NP-complete problems on planar graphs, in: Proceedings of the 24th IEEE Symposium on Foundations of Computer Science, FOCS, 1983, pp. 265-273; B.S. Baker, Approximation algorithms for NP-complete problems on planar graphs, in: Proceedings of the 24th IEEE Symposium on Foundations of Computer Science, FOCS, 1983, pp. 265-273 |
| [10] | Berman, F.; Johnson, D.; Leighton, T.; Shor, P. W.; Snyder, L., Generalized planar matching, Journal of Algorithms, 11, 153-184 (1990) · Zbl 0731.68041 |
| [11] | Beth, T.; Jungnickel, D.; Lenz, H., (Design Theory, vol. 2 (1999), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 0945.05005 |
| [12] | Bialostocki, A.; Roditty, Y., \(3 K_2\)-decomposition of a graph, Acta Mathematica Academiae Scientiarum Hungaricae, 40, 201-208 (1982) · Zbl 0467.05057 |
| [13] | Bollobás, B., Extremal Graph Theory (1978), Academic Press: Academic Press New York · Zbl 0419.05031 |
| [14] | Brouwer, A. E., Optimal packing of \(K_4\)’s into a \(K_n\), Journal of Combinatorial Theory, Series A, 26, 278-297 (1979) · Zbl 0412.05030 |
| [15] | A.E. Brouwer, R.M. Wilson, The decomposition of graphs into ladder graphs, Stiching Mathematisch Centrum (zn 97/80), Amsterdam, 1980; A.E. Brouwer, R.M. Wilson, The decomposition of graphs into ladder graphs, Stiching Mathematisch Centrum (zn 97/80), Amsterdam, 1980 |
| [16] | K. Bryś, Z. Lonc, A complete solution of a Holyer problem, in: Fourth Twente Workshop on Graph and Combinatorial Optimization, University of Twente, Enschede, The Netherlands, June 1995; K. Bryś, Z. Lonc, A complete solution of a Holyer problem, in: Fourth Twente Workshop on Graph and Combinatorial Optimization, University of Twente, Enschede, The Netherlands, June 1995 |
| [17] | Caprara, A.; Rizzi, R., Packing triangles in bounded degree graphs, Information Processing Letters, 84, 175-180 (2002) · Zbl 1042.68087 |
| [18] | Caro, Y., Decomposition of large combinatorial structures, Archiv der Mathematik, 52, 289-297 (1989) · Zbl 0653.05053 |
| [19] | Caro, Y.; Yuster, R., Packing Graphs: The packing problem solved, Electronic Journal of Combinatorics, 4, #R1 (1997) · Zbl 0885.05052 |
| [20] | Caro, Y.; Yuster, R., Graph decomposition of slim graphs, Graphs and Combinatorics, 15, 5-19 (1999) · Zbl 0937.05063 |
| [21] | Chen, G.; Lu, X.; West, D. B., Star-factors of tournaments, Journal of Graph Theory, 28, 141-145 (1998) · Zbl 0922.05030 |
| [22] | Coppersmith, D.; Winograd, S., Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, 9, 251-280 (1990) · Zbl 0702.65046 |
| [23] | Corrádi, K.; Hajnal, A., On the maximal number of independent circuits in a graph, Acta Mathematica Academiae Scientiarum Hungaricae, 14, 423-439 (1963) · Zbl 0118.19001 |
| [24] | Courcelle, B., The monadic second order logic of graphs III: Tree-decompositions, forbidden minors and complexity issues, Informatique Théorique et Applications, 26, 257-286 (1992) · Zbl 0754.03006 |
| [25] | O. Cooley, D. Kuhn, D. Osthus, Perfect packings with complete graphs minus an edge, European Journal of Combinatorics (in press); O. Cooley, D. Kuhn, D. Osthus, Perfect packings with complete graphs minus an edge, European Journal of Combinatorics (in press) · Zbl 1136.05055 |
| [26] | Dirac, G. A., Some theorems on abstract graphs, Proceedings of the London Mathematical Society, 2, 69-81 (1952) · Zbl 0047.17001 |
| [27] | Diestel, R., Graph theory, (Graduate Texts in Mathematics, vol. 173 (2005), Springer-Verlag: Springer-Verlag Heidelberg) · Zbl 0751.05002 |
| [28] | Dor, D.; Tarsi, M., Graph decomposition is NP-complete: A complete proof of Holyer’s Conjecture, SIAM Journal on Computing, 26, 1166-1187 (1997) · Zbl 0884.05071 |
| [29] | Edmonds, J., Paths, trees, and flowers, Canadian Journal of Mathematics, 17, 449-467 (1965) · Zbl 0132.20903 |
| [30] | El-Zahar, M. H., On Circuits in graphs, Discrete Mathematics, 50, 227-230 (1984) · Zbl 0548.05037 |
| [31] | P. Erdős, Some recent combinatorial problems, preprint, November 1990; P. Erdős, Some recent combinatorial problems, preprint, November 1990 |
| [32] | Erdős, P.; Rényi, A., On the existence of a factor of degree one of a connected random graph, Acta Mathematica Academiae Scientiarum Hungaricae, 17, 359-368 (1966) · Zbl 0203.56902 |
| [33] | Frankl, P.; Rödl, V., Near perfect coverings in graphs and hypergraphs, European Journal of Combinatorics, 6, 317-326 (1985) · Zbl 0624.05055 |
| [34] | Friedgut, E.; Kalai, G., Every monotone graph property has a sharp threshold, Proceedings of the American Mathematical Society, 124, 10, 2993-3002 (1996) · Zbl 0864.05078 |
| [35] | Frieze, A.; Kannan, R., A simple algorithm for constructing Szemerédi’s regularity partition, Electronic Journal of Combinatorics, 6, #R17 (1999) · Zbl 0917.05070 |
| [36] | Godsil, C.; Nešetřil, J.; Nowakowski, R., The chromatic connectivity of graphs, Graphs and Combinatorics, 4, 229-233 (1988) · Zbl 0657.05049 |
| [37] | Gowers, W. T., Lower bounds of tower type for Szemerédi’s uniformity lemma, Geometric and Functional Analysis, 7, 322-337 (1997) · Zbl 0876.05053 |
| [38] | Grable, D., Nearly-perfect hypergraph packing is in NC, Information Processing Letters, 60, 295-299 (1996) · Zbl 1336.68127 |
| [39] | T. Gustavsson, Decompositions of large graphs and digraphs with high minimum degree, Doctoral Dissertation, Dept. of Mathematics, Univ. of Stockholm, 1991; T. Gustavsson, Decompositions of large graphs and digraphs with high minimum degree, Doctoral Dissertation, Dept. of Mathematics, Univ. of Stockholm, 1991 |
| [40] | Haber, S.; Krivelevich, M., On fractional \(K\)-factors of random graphs, Random Structures and Algorithms, 30, 441-463 (2007) · Zbl 1120.05082 |
| [41] | Haxell, P. E.; Rödl, V., Integer and fractional packings in dense graphs, Combinatorica, 21, 13-38 (2001) · Zbl 1107.05304 |
| [42] | Hajnal, A.; Szemerédi, E., Proof of a conjecture of Erdős, (Erdös, P.; Renyi, A.; Sós, V. T., Combinatorial Theory and its Applications, vol. II. Combinatorial Theory and its Applications, vol. II, Colloq. Math. Soc. J. Bolyai, vol. 4 (1970), North Holland: North Holland Amsterdam), 601-623 · Zbl 0217.02601 |
| [43] | Holyer, I., The NP-completeness of some edge partition problems, SIAM Journal on Computing, 10, 713-717 (1981) · Zbl 0468.68069 |
| [44] | Hurkens, C. A.J.; Schrijver, A., On the size of systems of sets every \(t\) of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems, SIAM Journal on Discrete Mathematics, 2, 68-72 (1989) · Zbl 0733.05003 |
| [45] | Kann, V., Maximum bounded \(H\)-matching is MAX SNP-complete, Information Processing Letters, 49, 309-318 (1994) · Zbl 0803.68089 |
| [46] | Kawarabayashi, K., \(K_4^-\)-factors in a graph, Journal of Graph Theory, 39, 111-128 (2002) · Zbl 0992.05059 |
| [47] | H.A. Kierstead, A.V. Kostochka, A Short proof of the Hajnal-Szemerédi Theorem on equitable coloring, manuscript (2006); H.A. Kierstead, A.V. Kostochka, A Short proof of the Hajnal-Szemerédi Theorem on equitable coloring, manuscript (2006) |
| [48] | Kim, J. H., Perfect matchings in random uniform hypergraphs, Random Structures and Algorithms, 23, 111-132 (2003) · Zbl 1028.05088 |
| [49] | Kirkman, T. P., On a problem in combinatorics, Cambridge Dublin Mathematical Journal, 2, 191-204 (1847) |
| [50] | D.G. Kirkpatrick, P. Hell, On the complexity of a generalized matching problem, in: Proceedings of the \(10 t h\); D.G. Kirkpatrick, P. Hell, On the complexity of a generalized matching problem, in: Proceedings of the \(10 t h\) · Zbl 1282.68182 |
| [51] | Kohayakawa, Y.; Rödl, V.; Thoma, L., An optimal algorithm for checking regularity, SIAM Journal on Computing, 32, 1210-1235 (2003) · Zbl 1025.05056 |
| [52] | Komlós, J., Tiling Turán theorems, Combinatorica, 20, 203-218 (2000) · Zbl 0949.05063 |
| [53] | Komlós, J.; Sárkőzy, G. N.; Szemerédi, E., Blow-up lemma, Combinatorica, 17, 109-123 (1997) · Zbl 0880.05049 |
| [54] | Komlós, J.; Sárkőzy, G. N.; Szemerédi, E., Proof of the Seymour conjecture for large graphs, Annals of Combinatorics, 2, 43-60 (1998) · Zbl 0917.05043 |
| [55] | Komlós, J.; Sárkőzy, G. N.; Szemerédi, E., An algorithmic version of the Blow-up lemma, Random Structures and Algorithms, 12, 297-310 (1998) · Zbl 0917.05071 |
| [56] | Komlós, J.; Sárkőzy, G. N.; Szemerédi, E., Proof of the Alon-Yuster conjecture, Discrete Mathematics, 235, 255-269 (2001) · Zbl 0977.05106 |
| [57] | Komlós, J.; Simonovits, M., Szemerédi regularity lemma and its application in Graph Theory, (Paul Erdős is 80, Proc. Coll. Bolyai Math. Soc., vol. 2 (1996)), 295-352 · Zbl 0851.05065 |
| [58] | Krivelevich, M., Triangle factors in random graphs, Combinatorics, Probability, and Computing, 6, 337-347 (1997) · Zbl 0886.05101 |
| [59] | D. Kühn, D. Osthus, The minimum degree threshold for perfect graph packings, manuscript; D. Kühn, D. Osthus, The minimum degree threshold for perfect graph packings, manuscript |
| [60] | D. Kühn, D. Osthus, Critical chromatic number and the complexity of perfect packings in graphs, in: Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms, SODA, 2006, pp. 851-859; D. Kühn, D. Osthus, Critical chromatic number and the complexity of perfect packings in graphs, in: Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms, SODA, 2006, pp. 851-859 · Zbl 1192.05053 |
| [61] | Lonc, Z., Edge decomposition into isomorphic copies of \(s K_{1, 2}\), Journal of Combinatorial Theory, Series B, 69, 164-182 (1997) · Zbl 0868.05041 |
| [62] | Lovász, L., On determinants, matchings, and random algorithms, (Fundamentals of Computation Theory, vol. 2 (1979), Akademie-Verlag: Akademie-Verlag Berlin), 565-574 · Zbl 0446.68036 |
| [63] | Lovász, L.; Plummer, M. D., Matching Theory, (Annals of Discrete Mathematics, vol. 29 (1986), North-Holland) · Zbl 0618.05001 |
| [64] | S. Micali, V.V. Vazirani, An \(O ( \sqrt{ | V |} \cdot | E | )\); S. Micali, V.V. Vazirani, An \(O ( \sqrt{ | V |} \cdot | E | )\) |
| [65] | Minty, G. J., On maximal independent sets of vertices in claw-free graphs, Journal of Combinatorial Theory, Series B, 28, 284-304 (1980) · Zbl 0434.05043 |
| [66] | M. Mucha, P. Sankowski, Maximum matchings via Gaussian elimination, in: Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, FOCS, 2004, pp. 248-255; M. Mucha, P. Sankowski, Maximum matchings via Gaussian elimination, in: Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, FOCS, 2004, pp. 248-255 |
| [67] | M. Mydlarz, E. Szemerédi, Balanced coloring in polynomial time, European Journal of Combinatorics (in press); M. Mydlarz, E. Szemerédi, Balanced coloring in polynomial time, European Journal of Combinatorics (in press) |
| [68] | Nash-Williams, C. St. J.A., An unsolved problem concerning decomposition of graphs into triangles, (Erdös, P.; Rényi, P.; Sós, V. T., Combinatorial Theory and its Applications, vol. III (1970), North Holland), 1179-1183 |
| [69] | Priesler, M.; Tarsi, M., On the decomposition of the graphs into copies of \(P 3 \cup t K_2\), Ars Combinatoria, 35, 325-333 (1993) · Zbl 0779.05036 |
| [70] | Reid, K. B., Three problems on tournaments, (Graph Theory and its Applications: East and West (Proc. 2nd China-USA Intl. Conf. Graph Th., San Francisco 1989), vol. 576 (1989), New York Academy of Sciences Annals), 466-473 · Zbl 0792.05062 |
| [71] | Rödl, V., On a packing and covering problem, European Journal of Combinatorics, 6, 69-78 (1985) · Zbl 0565.05016 |
| [72] | Rödl, V.; Schacht, M.; Siggers, M. H.; Tokushige, N., Integer and fractional packings of hypergraphs, Journal of Combinatorial Theory, Series B, 97, 245-268 (2007) · Zbl 1111.05082 |
| [73] | Rucinski, A., Matching and covering the vertices of a random graph by copies of a given graph, Discrete Mathematics, 105, 185-197 (1992) · Zbl 0774.05091 |
| [74] | Shokoufandeh, A.; Zhao, Y., On a tiling conjecture of Komlós, Random Structures and Algorithms, 23, 180-205 (2003) · Zbl 1029.05121 |
| [75] | Stinson, D. R.; Ferch, H., 2000000 Steiner Triple Systems of order 19, Mathematics of Computation, 44, 533-535 (1985) · Zbl 0564.05011 |
| [76] | Szemerédi, E., Regular partitions of graphs, (Proc. Colloque Inter. CNRS, vol. 260 (1978), CNRS: CNRS Paris), 399-401 · Zbl 0413.05055 |
| [77] | Tutte, W. T., The factorization of linear graphs, Journal of the London Mathematical Society, 22, 107-111 (1947) · Zbl 0029.23301 |
| [78] | H. Wang, Proof of the Erdős-Faudree conjecture on quadrilaterals, manuscript; H. Wang, Proof of the Erdős-Faudree conjecture on quadrilaterals, manuscript · Zbl 1223.05145 |
| [79] | Wilson, R. M., Decomposition of complete graphs into subgraphs isomorphic to a given graph, Congressus Numerantium, XV, 647-659 (1975) · Zbl 0322.05116 |
| [80] | Yuster, R., Tree decomposition of graphs, Random Structures and Algorithms, 12, 237-251 (1998) · Zbl 0917.05059 |
| [81] | Yuster, R., Packing and decomposition of graphs with trees, Journal of Combinatorial Theory, Series B, 78, 123-140 (2000) · Zbl 1028.05095 |
| [82] | Yuster, R., The decomposition threshold of bipartite graphs with minimum degree one, Random Structures and Algorithms, 21, 121-134 (2002) · Zbl 1018.05090 |
| [83] | Yuster, R., Families of trees decompose the random graph in an arbitrary way, Combinatorics, Probability and Computing, 13, 893-910 (2004) · Zbl 1057.05070 |
| [84] | Yuster, R., Integer and fractional packing of families of graphs, Random Structures and Algorithms, 26, 110-118 (2005) · Zbl 1061.05076 |
| [85] | Yuster, R., Asymptotically optimal \(K_k\)-packing of dense graphs via fractional \(K_k\)-decomposition, Journal of Combinatorial Theory, Series B, 95, 1-11 (2005) · Zbl 1070.05071 |
| [86] | Yuster, R., Fractional decompositions of dense hypergraphs, Bulletin of the London Mathematical Society, 39, 156-166 (2007) · Zbl 1121.05080 |
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.
