Abstract
Treewidth is generally regarded as one of the most useful parameterizations of a graph’s construction. Clique-width is a similar parameterizations that shares one of the powerful properties of treewidth, namely: if a graph is of bounded treewidth (or clique-width), then there is a polynomial time algorithm for any graph problem expressible in Monadic Second Order Logic, using quantifiers on vertices (in the case of clique-width you must assume a clique-width parse expression is given). In studying the relationship between treewidth and clique-width, Courcelle and Olariu showed that any graph of bounded treewidth is also of bounded clique-width; in particular, for any graph G with treewidth k, the clique-width of G ≤ 4 * 2k−1 + 1.
In this paper, we improve this result to the clique-width of G ≤ 3 * 2k−1 and more importantly show that there is an exponential lower bound on this relationship. In particular, for any k, there is a graph G with treewidth = k where the clique-width of G ≥ 2[k/2]−1.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Arnborg, D. G. Corneil and A. Proskurowski, “Complexity of finding embeddings in a k-tree” SIAM J. Alg. Discrete Methods 8 (1987) 277–284.
H. L. Bodlaender, “A linear time algorithm for finding tree-decompositions of small treewidth” SIAM J. Comput. 25 (1996) 1305–1317.
A. Brandstädt and V.V. Lozin, “On the linear structure and clique-width of bipartite permutation graphs” Rutcor Research Report 29-2001 (2001).
D. G. Corneil, M. Habib, J. M. Lanlignel, B. Reed and U. Rotics, “Polynomial time recognition of clique-width ≤ 3 graphs (Extended Abstract)” accepted to Latin American Theoretical INformatic, LATIN’2000.
D. G. Corneil, Y. Perl and L. Stewart, “A linear recognition algorithm for cographs” SIAM J. Comput. 14 (1985) 926–934.
B. Courcelle, J. Engelfriet and G. Rozenberg, “Handle-rewriting hypergraphs grammars” J. Comput. System Sci. 46 (1993) 218–270.
B. Courcelle, J.A. Makowsky and U. Rotics, “Linear time solvable optimization problems on graphs of bounded clique-width” Theory of Computing Systems 33 (2000) 125–150.
B. Courcelle, J.A. Makowsky, and U. Rotics, “On the fixed parameter complexity of graph enumeration problems definable in monadic second order logic” to appear in Disc. Appl. Math.
B. Courcelle and S. Olariu, “Upper bounds to the clique-width of graphs” Disc. Appl. Math. 101 (2000) 77–114.
M.U. Gerber and D. Kobler, “Algorithms for vertex partitioning problems on graphs with fixed clique-width” submitted (2000).
M.C. Golumbic and U. Rotics, “On the clique-width of some perfect graph classes” Internat. J. Found. Comput. Sci 11 (2000) 423–443.
O. Johansson, “Clique-decomposition, NLC-decomposition, and modular decomposition-relationships and results for random graphs” Congressus Numerantium 132 (1998) 39–60.
D. Kobler and U. Rotics, “Polynomial algorithms for partitioning problems on graphs with fixed clique-width (Extended Abstract)” Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, (2001) 468–476.
J.A. Makowsky and U. Rotics, “On the classes of graphs with few P4’s” International Journal of Foundations of Computer Science 10 (1999) 329–348.
E. Wanke, “k-NLC graphs and polynomial algorithms” Discrete Applied Math. 54 (1994) 251–266.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Corneil, D.G., Rotics, U. (2001). On the Relationship between Clique-Width and Treewidth. In: Brandstädt, A., Le, V.B. (eds) Graph-Theoretic Concepts in Computer Science. WG 2001. Lecture Notes in Computer Science, vol 2204. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45477-2_9
Download citation
DOI: https://doi.org/10.1007/3-540-45477-2_9
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42707-0
Online ISBN: 978-3-540-45477-9
eBook Packages: Springer Book Archive