Approximating rank-width and clique-width quickly

ABSTRACT

Rank-width was defined by Oum and Seymour [2006] to investigate clique-width. They constructed an algorithm that either outputs a rank-decomposition of width at most f(k) for some function f or confirms that rank-width is larger than k in time O(|V|⁹log |V|) for an input graph G = (V,E) and a fixed k. We develop three separate algorithms of this kind with faster running time. We construct an O(|V|⁴)-time algorithm with f(k) = 3k + 1 by constructing a subroutine for the previous algorithm; we avoid generic algorithms minimizing submodular functions used by Oum and Seymour. Another one is an O(|V|³)-time algorithm with f(k) = 24k, achieved by giving a reduction from graphs to binary matroids; then we use an approximation algorithm for matroid branch-width by Hliněný [2005]. Finally we construct an O(|V|³)-time algorithm with f(k) = 3k − 1 by combining the ideas of the two previously cited papers.

REFERENCES

• 1: André Bouchet, Graphic presentations of isotropic systems, Journal of Combinatorial Theory Series A, v.45 n.1, p.58-76, July 1987
• 2: André Bouchet, Connectivity of isotropic systems, Proceedings of the third international conference on Combinatorial mathematics, p.81-93, September 1989, New York City, New York, United States
• 3: Bouchet, A. 1990. κ-transformations, local complementations and switching. In Cycles and Rays (Montreal, PQ, 1987). NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 301. Kluwer Academic, Dordrecht, Germany, 41--50.
• 4: André Bouchet, Circle graph obstructions, Journal of Combinatorial Theory Series B, v.60 n.1, p.107-144, Jan. 1994 [doi>10.1006/jctb.1994.1008]
• 5: Derek G. Corneil , Michel Habib , Jean-Marc Lanlignel , Bruce A. Reed , Udi Rotics, Polynomial Time Recognition of Clique-Width \le \leq 3 Graphs (Extended Abstract), Proceedings of the 4th Latin American Symposium on Theoretical Informatics, p.126-134, April 10-14, 2000
• 6: B. Courcelle, The expression of graph properties and graph transformations in monadic second-order logic, Handbook of graph grammars and computing by graph transformation: volume I. foundations, World Scientific Publishing Co., Inc., River Edge, NJ, 1997
• 7: Courcelle, B. 2006. The monadic second-order logic of graphs XV: On a conjecture by D. Seese. J. Appl. Log. 4, 1, 79--114.
• 8: Courcelle, B., Makowsky, J. A., and Rotics, U. 2000. Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33, 2, 125--150.
• 9: Bruno Courcelle , Stephan Olariu, Upper bounds to the clique width of graphs, Discrete Applied Mathematics, v.101 n.1-3, p.77-114, April 15, 2000 [doi>10.1016/S0166-218X(99)00184-5]
• 10: Bruno Courcelle , Sang-il Oum, Vertex-minors, monadic second-order logic, and a conjecture by Seese, Journal of Combinatorial Theory Series B, v.97 n.1, p.91-126, January, 2007 [doi>10.1016/j.jctb.2006.04.003]
• 11: Wolfgang Espelage , Frank Gurski , Egon Wanke, How to Solve NP-hard Graph Problems on Clique-Width Bounded Graphs in Polynomial Time, Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science, p.117-128, June 14-16, 2001
• 12: Michael R. Fellows , Frances A. Rosamond , Udi Rotics , Stefan Szeider, Clique-width minimization is NP-hard, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132568]
• 13: Geelen, J. F. 1995. Matchings, matroids and unimodular matrices. Ph.D. thesis, University of Waterloo.
• 14: Michael U. Gerber , Daniel Kobler, Algorithms for vertex-partitioning problems on graphs with fixed clique-width, Theoretical Computer Science, v.299 n.1-3, p.719-734, 18 April 2003 [doi>10.1016/S0304-3975(02)00725-9]
• 15: Illya V. Hicks , Nolan B. McMurray, Jr., The branchwidth of graphs and their cycle matroids, Journal of Combinatorial Theory Series B, v.97 n.5, p.681-692, September, 2007 [doi>10.1016/j.jctb.2006.12.007]
• 16: Petr Hlinený, A Parametrized Algorithm for Matroid Branch-Width, SIAM Journal on Computing, v.35 n.2, p.259-277, 2005 [doi>10.1137/S0097539702418589]
• 17: Petr Hliněný , Sang-il Oum, Finding Branch-Decompositions and Rank-Decompositions, SIAM Journal on Computing, v.38 n.3, p.1012-1032, June 2008 [doi>10.1137/070685920]
• 18: Satoru Iwata , Lisa Fleischer , Satoru Fujishige, A combinatorial strongly polynomial algorithm for minimizing submodular functions, Journal of the ACM (JACM), v.48 n.4, p.761-777, July 2001 [doi>10.1145/502090.502096]
• 19: Daniel Kobler , Udi Rotics, Edge dominating set and colorings on graphs with fixed clique-width, Discrete Applied Mathematics, v.126 n.2-3, p.197-221, 15 March 2003 [doi>10.1016/S0166-218X(02)00198-1]
• 20: Mazoit, F., and Thomassé, S. 2005. Branchwidth of graphic matroids. manuscript.
• 21: Sang-Il Oum , Paul Seymour, Graphs of bounded rank-width, Princeton University, Princeton, NJ, 2005
• 22: Sang-il Oum, Rank-width and vertex-minors, Journal of Combinatorial Theory Series B, v.95 n.1, p.79-100, September 2005 [doi>10.1016/j.jctb.2005.03.003]
• 23: Sang-il Oum , Paul Seymour, Approximating clique-width and branch-width, Journal of Combinatorial Theory Series B, v.96 n.4, p.514-528, July 2006 [doi>10.1016/j.jctb.2005.10.006]
• 24: Oxley, J. G. 1992. Matroid Theory. Oxford University Press, New York.
• 25: 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]
• 26: Seese, D. 1991. The structure of the models of decidable monadic theories of graphs. Ann. Pure Appl. Logic 53, 2, 169--195.
• 27: Seymour, P., and Thomas, R. 1994. Call routing and the ratcatcher. Combinatorica 14, 2, 217--241.
• 28: Egon Wanke, k-NLC graphs and polynomial algorithms, Discrete Applied Mathematics, v.54 n.2-3, p.251-266, Oct. 17, 1994 [doi>10.1016/0166-218X(94)90026-4]

INDEX TERMS

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

General Terms:
Algorithms, Theory

Keywords:
Approximation algorithms, branch-width, clique-width, matroids, rank-width