Catalan structures and dynamic programming in H-minor-free graphs

ABSTRACT

We give an algorithm that, for a fixed graph H and integer k, decides whether an n-vertex H-minor-free graph G contains a path of length k in 2O(√k). n^O(1) steps. Our approach builds on a combination of Demaine-Hajiaghayi's bounds on the size of an excluded grid in such graphs with a novel combinatorial result on certain branch decompositions of H-minor-free graphs. This result is used to bound the number of ways vertex disjoint paths can be routed through the separators of such decompositions. The proof is based on several structural theorems from the Graph Minors series of Robertson and Seymour. With a slight modification, similar combinatorial and algorithmic results can be derived for many other problems. Our approach can be viewed as a general framework for obtaining time 2^O(√k). n^O(1) algorithms on H-minor-free graph classes.

REFERENCES

• 1: J. Alber, H. L. Bodlaender, H. Fernau, T. Kloks, and R. Niedermeier, Fixed parameter algorithms for dominating set and related problems on planar graphs, Algorithmica, 33 (2002), pp. 461--493.
• 2: 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]
• 3: N. Alon, P. Seymour, and R. Thomas, A separator theorem for nonplanar graphs, J. Amer. Math. Soc., 3 (1990), pp. 801--808.
• 4: Noga Alon , Raphael Yuster , Uri Zwick, Color-coding, Journal of the ACM (JACM), v.42 n.4, p.844-856, July 1995 [doi>10.1145/210332.210337]
• 5: 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
• 6: William Cook , Paul Seymour, Tour Merging via Branch-Decomposition, INFORMS Journal on Computing, v.15 n.3, p.233-248, July 2003 [doi>10.1287/ijoc.15.3.233.16078]
• 7: A. Dawar, M. Grohe, and S. Kreutzer, Locally excluding a minor, preprint NI07001-LAA, Isaac Newton Institute of Mathematical Sciences, (2007).
• 8: V. G. Deineko, B. Klinz, and G. J. Woeginger, Exact algorithms for the Hamiltonian cycle problem in planar graphs, Oper. Res. Lett., 34 (2006), pp. 269--274.
• 9: 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]
• 10: 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]
• 11: E. D. Demaine and M. Hajiaghayi, The bidimensionality theory and its algorithmic applications, Computer Journal, to appear.
• 12: E. D. Demaine, Linearity of grid minors in treewidth with applications through bidimensionality, Combinatorica, to appear.
• 13: 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
• 14: Erik D. Demaine , MohammadTaghi Hajiaghayi , Bojan Mohar, Approximation algorithms via contraction decomposition, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.278-287, January 07-09, 2007, New Orleans, Louisiana
• 15: 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]
• 16: E. D. Demaine, M. T. Hajiaghayi, and D. M. Thilikos, Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors., Algorithmica, 41 (2005), pp. 245--267.
• 17: F. Dorn, F. V. Fomin, and D. M. Thilikos, Fast subexponential algorithm for non-local problems on graphs of bounded genus, in Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006), vol. 4059 of LNCS, Springer, Berlin, 2006, pp. 172--183.
• 18: F. Dorn, Catalan structures and dynamic programming in h-minor-free graphs, 2007. manuscript, http://www.ii.uib.no/publikasjoner/texrap/pdf/2007-357.pdf.
• 19: F. Dorn, E. Penninkx, H. Bodlaender, and F. V. Fomin, Efficient exact algorithms on planar graphs: Exploiting sphere cut branch decompositions, in Proceedings of the 13th Annual European Symposium on Algorithms (ESA 2005), vol. 3669 of LNCS, Springer, Berlin, 2005, pp. 95--106.
• 20: R. G. Downey and M. R. Fellows, Parameterized complexity, Springer-Verlag, New York, 1999.
• 21: J. Flum , M. Grohe, Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 22: Fedor V. Fomin , Dimitrios M. Thilikos, Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up, SIAM Journal on Computing, v.36 n.2, p.281-309, 2006 [doi>10.1137/S0097539702419649]
• 23: 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
• 24: Q.-P. Gu and H. Tamaki, Optimal branch-decomposition of planar graphs in O(n³) time, in Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005), vol. 3580 of LNCS, Springer, Berlin, 2005, pp. 373--384.
• 25: Russell Impagliazzo , Ramamohan Paturi , Francis Zane, Which problems have strongly exponential complexity?, Journal of Computer and System Sciences, v.63 n.4, p.512-530, December 2001 [doi>10.1006/jcss.2001.1774 ]
• 26: 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]
• 27: B. Mohar and C. Thomassen, Graphs on surfaces, Johns Hopkins University Press, Baltimore, MD, 2001.
• 28: R. Niedermeier, Invitation to fixed-parameter algorithms, vol. 31 of Oxford Lecture Series in Mathematics and its Applications, Oxford University Press, Oxford, 2006.
• 29: Christos H. Papadimitriou , Mihalis Yannakakis, On limited nondeterminism and the complexity of the V-C dimension, Journal of Computer and System Sciences, v.53 n.2, p.161-170, Oct. 1996 [doi>10.1006/jcss.1996.0058 ]
• 30: Neil Robertson , P. D. Seymour, Graph minors. VII. Disjoint paths on a surface, Journal of Combinatorial Theory Series B, v.45 n.2, p.212-254, Oct. 1988 [doi>10.1016/0095-8956(88)90070-6]
• 31: 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 ]
• 32: 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]
• 33: P. D. Seymour and R. Thomas, Call routing and the ratcatcher, Combinatorica, 14 (1994), pp. 217--241.
• 34: C. Thomassen, Embeddings of graphs with no short noncontractible cycles, Journal of Combinatorial Theory Series B, v.48 n.2, p.155-177, Apr. 1990 [doi>10.1016/0095-8956(90)90115-G]