Approximation algorithms via contraction decomposition

ABSTRACT

We prove that the edges of every graph of bounded (Euler) genus can be partitioned into any prescribed number k of pieces such that contracting any piece results in a graph of bounded treewidth (where the bound depends on k). This decomposition result parallels an analogous, simpler result for edge deletions instead of contractions, obtained in [Bak94, Epp00, DDO+04, DHK05], and it generalizes a similar result for "compression" (a variant of contraction) in planar graphs [Kle05]. Our decomposition result is a powerful tool for obtaining PTASs for contraction-closed problems (whose optimal solution only improves under contraction), a much more general class than minor-closed problems. We prove that any contraction-closed problem satisfying just a few simple conditions has a PTAS in bounded-genus graphs. In particular, our framework yields PTASs for the weighted Traveling Salesman Problem and for minimum-weight c-edge-connected submultigraph on bounded-genus graphs, improving and generalizing previous algorithms of [GKP95, AGK+98, Kle05, Gri00, CGSZ04, BCGZ05]. We also highlight the only main difficulty in extending our results to general H-minor-free graphs.

REFERENCES

• 1: Sanjeev Arora , Michelangelo Grigni , David Karger , Philip Klein , Andrzej Woloszyn, A polynomial-time approximation scheme for weighted planar graph TSP, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.33-41, January 25-27, 1998, San Francisco, California, United States
• 2: Eyal Amir, Efficient Approximation for Triangulation of Minimum Treewidth, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.7-15, August 02-05, 2001
• 3: Sanjeev Arora , Satish Rao , Umesh Vazirani, Expander flows, geometric embeddings and graph partitioning, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.222-231, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007355]
• 4: Brenda S. Baker, Approximation algorithms for NP-complete problems on planar graphs, Journal of the ACM (JACM), v.41 n.1, p.153-180, Jan. 1994 [doi>10.1145/174644.174650]
• 5: {BCGZ05} André Berger, Artur Czumaj, Michelangelo Grigni, and Hairong Zhao. Approximation schemes for minimum 2-connected spanning subgraphs in weighted planar graphs. In Proceedings of the 13th Annual European Symposium on Algorithms, volume 3669 of Lecture Notes in Computer Science, pages 472--483, Palma de Mallorca, Spain, October 2005.
• 6: Richard Brunet , Bojan Mohar , R. Bruce Richter, Separating and nonseparating disjoint homotopic cycles in graph embeddings, Journal of Combinatorial Theory Series B, v.66 n.2, p.201-231, March 1996 [doi>10.1006/jctb.1996.0016]
• 7: {Bod05} Hans L. Bodlaender. Discovering treewidth. In Proceedings of the 31st Conference on Current Trends in Theory and Practice of Computer Science, volume 3381 of Lecture Notes in Computer Science, pages 1--16, Liptovský Jan, Slovakia, January 2005.
• 8: Artur Czumaj , Michelangelo Grigni , Papa Sissokho , Hairong Zhao, Approximation schemes for minimum 2-edge-connected and biconnected subgraphs in planar graphs, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 9: {CM05} Sergio Cabello and Bojan Mohar. Finding shortest non-separating and non-contractible cycles for topologically embedded graphs. In Proceedings of the 13th Annual European Symposium on Algorithms, volume 3669 of Lecture Notes in Computer Science, pages 131--142, Palma de Mallorca, Spain, October 2005.
• 10: Matt DeVos , Guoli Ding , Bogdan Oporowski , Daniel P. Sanders , Bruce Reed , Paul Seymour , Dirk Vertigan, Excluding any graph as a minor allows a low tree-width 2-coloring, Journal of Combinatorial Theory Series B, v.91 n.1, p.25-41, May 2004 [doi>10.1016/j.jctb.2003.09.001]
• 11: Erik D. Demaine , Fedor V. Fomin , Mohammad Taghi Hajiaghayi , Dimitrios M. Thilikos, Bidimensional Parameters and Local Treewidth, SIAM Journal on Discrete Mathematics, v.18 n.3, p.501-511, 2005 [doi>10.1137/S0895480103433410]
• 12: Erik D. Demaine , Fedor V. Fomin , Mohammadtaghi Hajiaghayi , Dimitrios M. Thilikos, Fixed-parameter algorithms for (k, r)-center in planar graphs and map graphs, ACM Transactions on Algorithms (TALG), v.1 n.1, p.33-47, July 2005 [doi>10.1145/1077464.1077468]
• 13: Erik D. Demaine , Fedor V. Fomin , Mohammadtaghi Hajiaghayi , Dimitrios M. Thilikos, Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs, Journal of the ACM (JACM), v.52 n.6, p.866-893, November 2005 [doi>10.1145/1101821.1101823]
• 14: {DFT06} Frederic Dorn, Fedor V. Fomin, and Dimitrios M. Thilikos. Fast subexponential algorithm for non-local problems on graphs of bounded genus. In Proceedings of the 10th Scandinavian Workshop on Algorithm Theory, Riga, Latvia, July 2006. To appear.
• 15: {DH04a} Erik D. Demaine and MohammadTaghi Hajiaghayi. Diameter and treewidth in minor-closed graph families, revisited. Algorithmica, 40(3):211--215, August 2004.
• 16: Erik D. Demaine , MohammadTaghi Hajiaghayi, Equivalence of local treewidth and linear local treewidth and its algorithmic applications, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 17: Erik D. Demaine , Mohammad Taghi Hajiaghayi , Ken-ichi Kawarabayashi, Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.637-646, October 23-25, 2005 [doi>10.1109/SFCS.2005.14]
• 18: Erik D. Demaine , Mohammad Taghi Hajiaghayi , Naomi Nishimura , Prabhakar Ragde , Dimitrios M. Thilikos, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, Journal of Computer and System Sciences, v.69 n.2, p.166-166, September 2004 [doi>10.1016/j.jcss.2003.12.001]
• 19: Erik D. Demaine , MohammadTaghi Hajiaghayi , Dimitrios M. Thilikos, The Bidimensional Theory of Bounded-Genus Graphs, SIAM Journal on Discrete Mathematics, v.20 n.2, p.357-371, 2006 [doi>10.1137/040616929]
• 20: {Epp00} David Eppstein. Diameter and treewidth in minor-closed graph families. Algorithmica, 27(3--4):275--291, 2000.
• 21: Uriel Feige , Joe Kilian, Zero knowledge and the chromatic number, Journal of Computer and System Sciences, v.57 n.2, p.187-199, Oct. 1998 [doi>10.1006/jcss.1998.1587]
• 22: {FT04} Fedor V. Fomin and Dimitrios M. Thilikos. Fast parameterized algorithms for graphs on surfaces: Linear kernel and exponential speed-up. In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP 2004), pages 581--592, Turku, Finland, July 2004.
• 23: John R. Gilbert , Joan P. Hutchinson , Robert Endre Tarjan, A separator theorem for graphs of bounded genus, Journal of Algorithms, v.5 n.3, p.391-407, Sept. 1984 [doi>10.1016/0196-6774(84)90019-1]
• 24: M. Grigni , E. Koutsoupias , C. Papadimitriou, An approximation scheme for planar graph TSP, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.640, October 23-25, 1995
• 25: Michelangelo Grigni, Approximate TSP in Graphs with Forbidden Minors, Proceedings of the 27th International Colloquium on Automata, Languages and Programming, p.869-877, July 09-15, 2000
• 26: Martin Grohe, Local Tree-Width, Excluded Minors, and Approximation Algorithms, Combinatorica, v.23 n.4, p.613-632, December 2003 [doi>10.1007/s00493-003-0037-9]
• 27: Michelangelo Grigni , Papa Sissokho, Light spanners and approximate TSP in weighted graphs with forbidden minors, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.852-857, January 06-08, 2002, San Francisco, California
• 28: Jonathan A. Kelner, Spectral Partitioning, Eigenvalue Bounds, and Circle Packings for Graphs of Bounded Genus, SIAM Journal on Computing, v.35 n.4, p.882-902, 2006 [doi>10.1137/S0097539705447244]
• 29: Philip N. Klein, A linear-time approximation scheme for planar weighted TSP, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.647-657, October 23-25, 2005 [doi>10.1109/SFCS.2005.7]
• 30: Philip N. Klein, A subset spanner for Planar graphs,: with application to subset TSP, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132620]
• 31: Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999 [doi>10.1145/331524.331526]
• 32: {LT80} Richard J. Lipton and Robert Endre Tarjan. Applications of a planar separator theorem. SIAM Journal on Computing, 9(3):615--627, 1980.
• 33: {Moh92} Bojan Mohar. Combinatorial local planarity and the width of graph embeddings. Canadian Journal of Mathematics, 44(6):1272--1288, 1992.
• 34: Bojan Mohar, A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface, SIAM Journal on Discrete Mathematics, v.12 n.1, p.6-26, Jan. 1999 [doi>10.1137/S089548019529248X]
• 35: {Moh01} Bojan Mohar. Graph minors and graphs on surfaces. In Surveys in Combinatorics, volume 288 of London Math. Soc. Lecture Note Ser., pages 145--163. Cambridge Univ. Press, Cambridge, 2001.
• 36: {MT01} Bojan Mohar and Carsten Thomassen. Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, 2001.
• 37: {RS86} Neil Robertson and Paul D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms, 7(3):309--322, 1986.
• 38: Neil Robertson , P. D. Seymour, Graph minors. XI.: circuits on a surface, Journal of Combinatorial Theory Series B, v.60 n.1, p.72-106, Jan. 1994 [doi>10.1006/jctb.1994.1007]
• 39: Neil Robertson , P. D. Seymour, Graph minors. XVI. excluding a non-planar graph, Journal of Combinatorial Theory Series B, v.89 n.1, p.43-76, September 2003 [doi>10.1016/S0095-8956(03)00042-X]
• 40: {Tho95} Robin Thomas. Problem Session of the 3rd Solvene Conference on Graph Theory, Bled, Slovenia, 1995.
• 41: Mikkel Thorup, All structured programs have small tree width and good register allocation, Information and Computation, v.142 n.2, p.159-181, May 2, 1998 [doi>10.1006/inco.1997.2697]
• 42: {Wag37} K. Wagner. Über eine Eigenschaft der eben Komplexe. Mathematische Annalen, 114:570--590, December 1937.