Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs

ABSTRACT

We introduce a new framework for designing fixed-parameter algorithms with subexponential running time---2^O(&kradic;) n^O(1). Our results apply to a broad family of graph problems, called bidimensional problems, which includes many domination and problems such as vertex cover, feedback vertex set, minimum maximal matching, dominating set, edge dominating set, disk dimension, and many others restricted to bounded-genus graphs (phrased as bipartite-graph problem). Furthermore, it is fairly straightforward to prove that a problem is bidimensional. In particular, our framework includes, as special cases, all previously known problems to have such subexponential algorithms. Previously, these algorithms applied to planar graphs, single-crossing-minor-free graphs, and/or map graphs; we extend these results to apply to bounded-genus graphs as well. In a parallel development of combinatorial results, we establish an upper bound on the treewidth (or branchwidth) of a bounded-genus graph that excludes some planar graph H as a minor. This bound depends linearly on the size ¦V(H)¦ of the excluded graph H and the genus g(G) of the graph G, and applies and extends the graph-minors work of Robertson and Seymour.Building on these results, we develop subexponential fixed-parameter algorithms for dominating set, vertex cover, and set cover in any class of graphs excluding a fixed graph H as a minor. In particular, this general category of graphs includes planar graphs, bounded-genus graphs, single-crossing-minor-free graphs, and any class of graphs that is closed under taking minors. Specifically, the running time is 2^O(&kracic;) n^h, where h is a constant depending only on H, which is polynomial for k = O(log² n). We introduce a general approach for developing algorithms on H-minor-free graphs, based on structural results about H-minor-free graphs at the heart of Robertson and Seymour's graph-minors work. We believe this approach opens the way to further development on problems in H-minor-free graphs.

REFERENCES

• 1: Alber, J., Bodlaender, H. L., Fernau, H., Kloks, T., and Niedermeier, R. 2002. Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica 33, 4, 461--493.
• 2: Jochen Alber , Hongbing Fan , Michael R. Fellows , Henning Fernau , Rolf Niedermeier , Frances A. Rosamond , Ulrike Stege, Refined Search Tree Technique for DOMINATING SET on Planar Graphs, Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science, p.111-122, August 27-31, 2001
• 3: Jochen Alber , Michael R. Fellows , Rolf Niedermeier, Polynomial-time data reduction for dominating set, Journal of the ACM (JACM), v.51 n.3, p.363-384, May 2004 [doi>10.1145/990308.990309]
• 4: Jochen Alber , Henning Fernau , Rolf Niedermeier, Parameterized complexity: exponential speed-up for planar graph problems, Journal of Algorithms, v.52 n.1, p.26-56, July 2004 [doi>10.1016/j.jalgor.2004.03.005]
• 5: 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
• 6: Thomas Böhme , John Maharry , Bojan Mohar, Ka,k minors in graphs of bounded tree-width, Journal of Combinatorial Theory Series B, v.86 n.1, p.133-147, September 2002 [doi>10.1006/jctb.2002.2119]
• 7: John Adrian Bondy, Graph Theory With Applications, Elsevier Science Ltd, 1976
• 8: Cai, L., Fellows, M., Juedes, D., and Rosamond, F. 2001. On efficient polynomial-time approximation schemes for problems on planar structures. Manuscript.
• 9: Liming Cai , David Juedes, On the existence of subexponential parameterized algorithms, Journal of Computer and System Sciences, v.67 n.4, p.789-807, December 2003 [doi>10.1016/S0022-0000(03)00074-6]
• 10: L. Sunil Chandran , Fabrizio Grandoni, Refined memorization for vertex cover, Information Processing Letters, v.93 n.3, p.125-131, 14 February 2005 [doi>10.1016/j.ipl.2004.10.003]
• 11: Maw-Shang Chang , Ton Kloks , Chuan-Min Lee, Maximum Clique Transversals, Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science, p.32-43, June 14-16, 2001
• 12: Moses Charikar , Amit Sahai, Dimension Reduction in the \ell _1 Norm, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.551-560, November 16-19, 2002
• 13: Chandra Chekuri , Anupam Gupta , Ilan Newman , Yuri Rabinovich , Alistair Sinclair, Embedding k-outerplanar graphs into ℓ1, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 14: 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]
• 15: 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]
• 16: Demaine, E. D., and Hajiaghayi, M. 2004a. Diameter and treewidth in minor-closed graph families, revisited. Algorithmica 40, 3 (Aug.), 211--215.
• 17: 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
• 18: Erik D. Demaine , MohammadTaghi Hajiaghayi, Bidimensionality: new connections between FPT algorithms and PTASs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 19: Erik D. Demaine , MohammadTaghi Hajiaghayi, Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 20: 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]
• 21: 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]
• 22: Erik D. Demaine , Mohammad Taghi Hajiaghayi , Dimitrios M. Thilikos, -Approximation for Treewidth of Graphs Excluding a Graph with One Crossing as a Minor, Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, p.67-80, September 17-21, 2002
• 23: Demaine, E. D., Hajiaghayi, M., and Thilikos, D. M. 2004b. The bidimensional theory of bounded-genus graphs. In Proceedings of the 29th International Symposium on Mathematical Foundations of Computer Science (MFCS 2004). 191--203.
• 24: Demaine, E. D., Hajiaghayi, M., and Thilikos, D. M. 2005c. Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors. Algorithmica 41, 4 (Feb.), 245--267.
• 25: 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]
• 26: Reinhard Diestel , Robin Thomas, Excluding a countable clique, Journal of Combinatorial Theory Series B, v.76 n.1, p.41-67, May 1999 [doi>10.1006/jctb.1998.1886 ]
• 27: Downey, R. G., and Fellows, M. R. 1999. Parameterized Complexity. Springer-Verlag, New York.
• 28: J. Ellis , H. Fan , M. Fellows, The dominating set problem is fixed parameter tractable for graphs of bounded genus, Journal of Algorithms, v.52 n.2, p.152-168, August 2004 [doi>10.1016/j.jalgor.2004.02.001]
• 29: Michael R. Fellows, Parameterized Complexity: The Main Ideas and Some Research Frontiers, Proceedings of the 12th International Symposium on Algorithms and Computation, p.291-307, December 19-21, 2001
• 30: Fedor V. Fomin , Dimitrios M. Thilikos, Dominating sets in planar graphs: branch-width and exponential speed-up, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 31: Fomin, F. V., and Thilikos, D. M. 2004. 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) (Turku, Finland). 581--592.
• 32: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 33: 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]
• 34: Jörg Flum , Martin Grohe, The Parameterized Complexity of Counting Problems, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.538, November 16-19, 2002
• 35: Anupam Gupta , Alistair Sinclair , Ilan Newman , Yuri Rabinovich, Cuts, Trees and -Embeddings of Graphs, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.399, October 17-18, 1999
• 36: Gutin, G., Kloks, T., and Lee, C. M. 2001. Kernels in planar digraphs. In Optimization Online. Mathematical Programming Society, Philadelphia, PA.
• 37: Haynes, T. W., Hedetniemi, S. T., and Slater, P. J. 1998. Fundamentals of Domination in Graphs. Marcel Dekker Inc.
• 38: Iyad Kanj , Ljubomir Perkovic, Improved Parameterized Algorithms for Planar Dominating Set, Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science, p.399-410, August 26-30, 2002
• 39: Philip Klein , Serge A. Plotkin , Satish Rao, Excluded minors, network decomposition, and multicommodity flow, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.682-690, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167261]
• 40: Ton Kloks , C. M. Lee , Jiping Liu, New Algorithms for k-Face Cover, k-Feedback Vertex Set, and k -Disjoint Cycles on Plane and Planar Graphs, Revised Papers from the 28th International Workshop on Graph-Theoretic Concepts in Computer Science, p.282-295, June 13-15, 2002
• 41: Mohar, B., and Thomassen, C. 2001. Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD.
• 42: Serge Plotkin , Satish Rao , Warren D. Smith, Shallow excluded minors and improved graph decompositions, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.462-470, January 23-25, 1994, Arlington, Virginia, United States
• 43: Robertson, N., and Seymour, P. D. 1986a. Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7, 3, 309--322.
• 44: Neil Robertson , P D Seymour, Graph minors. V. Excluding a planar graph, Journal of Combinatorial Theory Series B, v.41 n.1, p.92-114, Aug. 1986 [doi>10.1016/0095-8956(86)90030-4]
• 45: Neil Robertson , P. D. Seymour, Graph minors: X. obstructions to tree-decomposition, Journal of Combinatorial Theory Series B, v.52 n.2, p.153-190, July 1991 [doi>10.1016/0095-8956(91)90061-N]
• 46: 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 ]
• 47: Neil Robertson , P. D. Seymour, Graph minors. XII: distance on a surface, Journal of Combinatorial Theory Series B, v.64 n.2, p.240-272, July 1995 [doi>10.1006/jctb.1995.1034 ]
• 48: Neil Robertson , P. D. Seymour, Graph minors. XIII: the disjoint paths problem, Journal of Combinatorial Theory Series B, v.63 n.1, p.65-110, Jan. 1995 [doi>10.1006/jctb.1995.1006 ]
• 49: 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]
• 50: Neil Robertson , Paul Seymour , Robin Thomas, Quickly excluding a planar graph, Journal of Combinatorial Theory Series B, v.62 n.2, p.323-348, Nov. 1994 [doi>10.1006/jctb.1994.1073 ]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems; Graph algorithms

Keywords:
(k, r)-center, domination, fixed-parameter algorithms, map graph, planar graph