TY - CHAP

T1 - A simple and fast approach for solving problems on planar graphs

AU - Fomin, Fedor V.

AU - Thilikos, Dimtirios M.

PY - 2004

Y1 - 2004

N2 - 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°(√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, INDEPENDENT SET on planar graphs can be solved in time O(23.182√nn + n 4) and DOMINATING SET in time O(25.043√nn + n 4). In addition, significantly broader class of problems can be attacked by this method. Thus with our approach, LONGEST CYCLE on planar graphs is solved in time O(22.29√n(ln n+0.94)n5/4 + n 4) and BISECTION is solved in time O(2 3.182√nn+n4). 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√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 VERTEX COVER, (WEIGHTED) DOMINATING SET, and many others.

AB - 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°(√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, INDEPENDENT SET on planar graphs can be solved in time O(23.182√nn + n 4) and DOMINATING SET in time O(25.043√nn + n 4). In addition, significantly broader class of problems can be attacked by this method. Thus with our approach, LONGEST CYCLE on planar graphs is solved in time O(22.29√n(ln n+0.94)n5/4 + n 4) and BISECTION is solved in time O(2 3.182√nn+n4). 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√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 VERTEX COVER, (WEIGHTED) DOMINATING SET, and many others.

UR - http://www.scopus.com/inward/record.url?scp=35048828350&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=35048828350&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-24749-4_6

DO - 10.1007/978-3-540-24749-4_6

M3 - Chapter

AN - SCOPUS:35048828350

SN - 9783540212362

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 56

EP - 67

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Diekert, Volker

A2 - Habib, Michel

PB - Springer Verlag

ER -