Dominating sets in planar graphs: branch-width and exponential speed-up

ABSTRACT

Graph minors theory, developed by Robertson & Seymour, provides a list of powerful theoretical results and tools. However, the wide spread opinion in Graph Algorithms community about this theory is that it is mainly of theoretical importance. The main purpose of this paper is to show how very deep min-max and duality theorems from Graph Minors can be used to obtain essential speed-up to many known algorithms on different domination problems.

REFERENCES

• 1: J. ALBER, H. L. BODLAENDER, H. FERNAU, T. KLOKSAND R. NIEDERMEIER, Fixed parameter algorithms for dominating set and related problems on planar graphs, Algorithmica, 33 (2002), pp. 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, Efficient Data Reduction for DOMINATING SET: A Linear Problem Kernel for the Planar Case, Proceedings of the 8th Scandinavian Workshop on Algorithm Theory, p.150-159, July 03-05, 2002
• 4: J. ALBER, H. FERNAU, AND R. NIEDERMEIER, Parameterized complexity: Exponential speed-up for planar graph problems, in Electronic Colloquium on Computational Complexity (ECCC), Germany, 2001.
• 5: Michael Alekhnovich , Alexander A. Razborov, Satisfiability, Branch-Width and Tseitin Tautologies, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.593-603, November 16-19, 2002
• 6: Noga Alon , Paul Seymour , Robin Thomas, Planar Separators, SIAM Journal on Discrete Mathematics, v.7 n.2, p.184-193, May 1994 [doi>10.1137/S0895480191198768]
• 7: Hans L. Bodlaender , Dimitrios M. Thilikos, Graphs with branchwidth at most three, Journal of Algorithms, v.32 n.2, p.167-194, Aug. 1999 [doi>10.1006/jagm.1999.1011]
• 8: 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
• 9: Erik D. Demaine , Mohammad Taghi Hajiaghayi , Dimitrios M. Thilikos, Exponential Speedup of Fixed-Parameter Algorithms on K3, 3-Minor-Free or K5-Minor-Free Graphs, Proceedings of the 13th International Symposium on Algorithms and Computation, p.262-273, November 21-23, 2002
• 10: R. G. DOWNEYAND M. R. FELLOWS, Parameterized complexity, Springer-Verlag, New York, 1999.
• 11: F. V. FOMINAND D. M. THILIKOS, New upper bounds on the decomposability of planar graphs and fixed parameter algorithms, technical report, Universitat Politècnica de Catalunya, Spain, 2002.
• 12: James F. Geelen , A. M. H. Gerards , Geoff Whittle, Branch-width and well-quasi-ordering in matroids and graphs, Journal of Combinatorial Theory Series B, v.84 n.2, p.270-290, March 2002 [doi>10.1006/jctb.2001.2082]
• 13: T. W. HAYNES, S. T. HEDETNIEMI, AND P. J. SLATER, Fundamentals of domination in graphs, Marcel Dekker Inc., New York, 1998.
• 14: I. V. HICKS, Branch Decompositions and their applications, PhD thesis, Rice University, 2000.
• 15: P. HLINENY, Branch-width, parse trees, and secondorder monadic logic for matroids over finite fields. manuscript, 2002.
• 16: 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
• 17: T. KLOKSAND L. CAI, Parameterized tractability of some (efficient) Y-domination variants for planar graphs and t-degenerate graphs, in International Computer Symposium (ICS), Taiwan, 2000.
• 18: 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]
• 19: 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]
• 20: 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]
• 21: P. D. SEYMOURAND R. THOMAS, Call routing and the ratcatcher, Combinatorica, 14 (1994), pp. 217--241.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.m Miscellaneous

General Terms:
Algorithms, Theory

Keywords:
Branch-width, Dominating Set, Fixed Parameter Algorithm, Planar Graph, Tree-width