ALCOMFT-TR-03-106

Fedor V. Fomin and Dimitrios M. Thilikos
A Simple and Fast Approach for Solving Problems on Planar Graphs
Barcelona. Work packages 2 and 4. November 2003.

Abstract: It is well known that the celebrated Lipton-Tarjan planar separation theorem, in a combination with a divide-and-conquer strategy leads to many complexity results for planar graph problems. For example, by using this approach, many planar graph problems can be solved in time 2^O(\sqrt{n}), where n is the number of vertices. However, the constants hidden in big-Oh, usually are too large to claim the algorithms to be practical even on graphs of moderate size. Here we introduce a new algorithm design paradigm for solving problems on planar graphs. The paradigm is so simple that it can be explained in any textbook on graph algorithms: Compute tree or branch decomposition of a planar graph and do dynamic programming. Surprisingly such a simple approach provides faster algorithms for many problems. For example, \textscIndependent Set on planar graphs can be solved in time O(2^{3.182\sqrt{n}}n+n⁴) and \textscDominating Set in time O(2^{5.043\sqrt{n}}n+n⁴). In addition, significantly broader class of problems can be attacked by this method. Thus with our approach, \textscLongest cycle on planar graphs is solved in time O(2^{2.29\sqrt{n}(\lnn+0.94)}n^5/4+n⁴) and \textscBisection is solved in time O(2^{3.182\sqrt{n}}n+n⁴). The proof of these results is based on complicated combinatorial arguments that make strong use of results derived by the Graph Minors Theory. In particular we prove that branch-width of a planar graph is at most 2.122\sqrt{n}. In addition we observe how a similar approach can be used for solving different fixed parameter problems on planar graphs. We prove that our method provides the best so far exponential speed-up for fundamental problems on planar graphs like \textscVertex Cover, \textsc(Weighted) Dominating Set, and many others.

Postscript file: ALCOMFT-TR-03-106.ps.gz (264 kb).