Clique-width: on the price of generality

ABSTRACT

Many hard problems can be solved efficiently when the input is restricted to graphs of bounded treewidth. By the celebrated result of Courcelle, every decision problem expressible in monadic second order logic is fixed parameter tractable when parameterized by the treewidth of the input graph. Moreover, for every fixed k ≥ 0, such problems can be solved in linear time on graphs of treewidth at most k. In particular, this implies that basic problems like Dominating Set, Graph Coloring, Clique, and Hamiltonian Cycle are solvable in linear time on graphs of bounded treewidth.

A significant amount of research in graph algorithms has been devoted to extending this result to larger classes of graphs. It was shown that some of the algorithmic meta-theorems for treewidth can be carried over to graphs of bounded clique-width. Courcelle, Makowsky, and Rotics proved that the analogue of Courcelle's result holds for graphs of bounded clique-width when the logical formulas do not use edge set quantifications. Despite of its generality, this does not resolve the parameterized complexity of many basic problems concerning edge subsets (like Edge Dominating Set), vertex partitioning (like Graph Coloring), or global connectivity (like Hamiltonian Cycle). There are various algorithms solving some of these problems in polynomial time on graphs of clique-width at most k. However, these are not fixed parameter tractable algorithms and have typical running times O(n^f(k)), where n is the input length and f is some function.

It was an open problem, explicitly mentioned in several papers, whether any of these problems is fixed parameter tractable when parameterized by the clique-width, i.e. solvable in time O(g(k)·n^c), for some function g and a constant c not depending on k. In this paper we resolve this problem by showing that Edge Dominating Set, Hamiltonian Cycle, and Graph Coloring are W[1]-hard parameterized by clique-width. This shows that the running time O(n^f(k)) of many clique-width based algorithms is essentially the best we can hope for (up to a widely believed assumption from parameterized complexity, namely FPT ≠ W[1])---the price we pay for generality.

REFERENCES

• 1: Stefan Arnborg , Jens Lagergren , Detlef Seese, Easy problems for tree-decomposable graphs, Journal of Algorithms, v.12 n.2, p.308-340, June 1991 [doi>10.1016/0196-6774(91)90006-K]
• 2: Hans L. Bodlaender, A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth, SIAM Journal on Computing, v.25 n.6, p.1305-1317, Dec. 1996 [doi>10.1137/S0097539793251219]
• 3: Hans L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth, Theoretical Computer Science, v.209 n.1-2, p.1-45, Dec. 6, 1998 [doi>10.1016/S0304-3975(97)00228-4]
• 4: 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
• 5: Derek G. Corneil , Udi Rotics, On the Relationship Between Clique-Width and Treewidth, SIAM Journal on Computing, v.34 n.4, p.825-847, 2005 [doi>10.1137/S0097539701385351]
• 6: B. Courcelle, The monadic second-order logic of graphs. III. Tree-decompositions, minors and complexity issues, RAIRO Inform. Théor. Appl., 26 (1992), pp. 257--286.
• 7: B. Courcelle, J. A. Makowsky, and U. Rotics, Linear time solvable optimization problems on graphs of bounded clique-width, Theory Comput. Syst., 33 (2000), pp. 125--150.
• 8: B. Courcelle , J. A. Makowsky , U. Rotics, On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic, Discrete Applied Mathematics, v.108 n.1, p.23-52, Feb. 15,2001 [doi>10.1016/S0166-218X(00)00221-3]
• 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: M. Dom, D. Lokshtanov, S. Saurabh, and Y. Villanger, Capacitated domination and covering: A parameterized perspective, in IWPEC'08, vol. 5018 of LNCS, Springer, 2008, pp. 78--90.
• 11: R. G. Downey and M. R. Fellows, Parameterized complexity, Monographs in Computer Science, Springer-Verlag, New York, 1999.
• 12: 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
• 13: W. Espelage, F. Gurski, and E. Wanke, Deciding clique-width for graphs of bounded tree-width, J. Graph Algorithms Appl., 7 (2003), pp. 141--180 (electronic).
• 14: M. R. Fellows, F. V. Fomin, D. Lokshtanov, F. A. Rosamond, S. Saurabh, S. Szeider, and C. Thomassen, On the complexity of some colorful problems parameterized by treewidth, in COCOA, 2007, pp. 366--377.
• 15: 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]
• 16: 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]
• 17: Omer Gime´nez , Petr Hlineˇny´ , Marc Noy, Computing the Tutte Polynomial on Graphs of Bounded Clique-Width, SIAM Journal on Discrete Mathematics, v.20 n.4, p.932-946, December 2006 [doi>10.1137/050645208]
• 18: Benny Godlin , Tomer Kotek , Johann A. Makowsky, Evaluations of Graph Polynomials, Graph-Theoretic Concepts in Computer Science: 34th International Workshop, WG 2008, Durham, UK, June 30 --- July 2, 2008. Revised Papers, Springer-Verlag, Berlin, Heidelberg, 2008 [doi>10.1007/978-3-540-92248-3_17]
• 19: P. Hlinený, S. il Oum, D. Seese, and G. Gottlob, Width parameters beyond tree-width and their applications, Comput. J., 51 (2008), pp. 326--362.
• 20: Sang-Il Oum, Approximating rank-width and clique-width quickly, ACM Transactions on Algorithms (TALG), v.5 n.1, p.1-20, November 2008 [doi>10.1145/1435375.1435385]
• 21: Daniel Kobler , Udi Rotics, Polynomial algorithms for partitioning problems on graphs with fixed clique-width (extended abstract), Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.468-476, January 07-09, 2001, Washington, D.C., United States
• 22: 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]
• 23: J. Makowsky, U. Rotics, I. Averbouch, and B. Godlin, Computing graph polynomials on graphs of bounded clique-width, in WG'06, LNCS, Springer, 2006, pp. 191--204.
• 24: 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]
• 25: Michaël Rao, MSOL partitioning problems on graphs of bounded treewidth and clique-width, Theoretical Computer Science, v.377 n.1-3, p.260-267, May, 2007 [doi>10.1016/j.tcs.2007.03.043]
• 26: Karol Suchan , Ioan Todinca, On powers of graphs of bounded NLC-width (clique-width), Discrete Applied Mathematics, v.155 n.14, p.1885-1893, September, 2007 [doi>10.1016/j.dam.2007.03.014]
• 27: 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

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms