×

zbMATH — the first resource for mathematics

From tree-decompositions to clique-width terms. (English) Zbl 1395.05097
Summary: Tree-width and clique-width are two important graph complexity measures that serve as parameters in many fixed-parameter tractable algorithms. We give two algorithms that transform tree-decompositions represented by normal trees into clique-width terms (a rooted tree is normal for a graph if its nodes are the vertices of the graph and every two adjacent vertices are on a path of the tree starting at the root). As a consequence, we obtain that, for certain classes of sparse graphs, clique-width is polynomially bounded in terms of tree-width. It is even linearly bounded for planar graphs and incidence graphs. These results are useful in the construction of model-checking algorithms for problems described by monadic second-order formulae, including those allowing edge set quantifications.

MSC:
05C42 Density (toughness, etc.)
05C10 Planar graphs; geometric and topological aspects of graph theory
05C12 Distance in graphs
05C85 Graph algorithms (graph-theoretic aspects)
Software:
ComputeTW
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arnborg, S.; Corneil, D.; Proskurowski, A., Complexity of finding embeddings in a \(k\)-tree, SIAM J. Algebr. Discrete Methods, 8, 277-284, (1987) · Zbl 0611.05022
[2] Bodlaender, H., A partial k-arboretum of graphs with bounded treewidth, Theoret. Comput. Sci., 209, 1-45, (1998) · Zbl 0912.68148
[3] Bodlaender, H.; Drange, P.; Dregi, M.; Fomin, F.; Lokshtanov, D.; Pilipczuk, M., A \(c^k n\) 5-approximation algorithm for treewidth, SIAM J. Comput., 45, 317-378, (2016) · Zbl 1333.05282
[4] Bodlaender, H.; Koster, A., Treewidth computations I. upper bounds, Inform. and Comput., 208, 259-275, (2010) · Zbl 1186.68328
[5] Bodlaender, H.; Kratsch, S.; Kreuzen, V., Fixed-parameter tractability and characterizations of small special treewidth, Proc. WG Lect. Notes Comput. Sci., 8165, 88-99, (2013) · Zbl 1400.05234
[6] Bodlaender, H.; Kratsch, S.; Kreuzen, V.; Kwon, O.; Ok, S., Characterizing width two for variants of treewidth, Discrete Appl. Math., 216, 29-46, (2017) · Zbl 1350.05116
[7] T. Bouvier, Graphes et décompositions (Doctoral dissertation), Bordeaux University, 2014.
[8] Bui-Xuan, B.; Telle, J.; Vatshelle, M., Boolean-width of graphs, Theoret. Comput. Sci., 412, 5187-5204, (2011) · Zbl 1225.68133
[9] Corneil, D.; Rotics, U., On the relationship between clique-width and tree-width, SIAM J. Comput., 34, 825-847, (2005) · Zbl 1069.05067
[10] Courcelle, B., On the model-checking of monadic second-order formulas with edge set quantifications, Discrete Appl. Math., 160, 866-887, (2012) · Zbl 1236.05143
[11] Courcelle, B., Fly-automata for checking monadic second-order properties of graphs of bounded tree-width, Electron. Notes Discrete Math., 50, 3-8, (2015), Proceedings of LAGOS 2015, Beberibe, Brazil; a long version is in http://www.labri.fr/perso/courcell/Conferences/BC-Lagos2015.pdf · Zbl 1347.03077
[12] Courcelle, B., Fly-automata for checking MSO_2 graph properties, Discrete Appl. Math., (2016), https://hal.archives-ouvertes.fr/hal-01234622v2, in press
[13] Courcelle, B.; Durand, I., Automata for the verification of monadic second-order graph properties, J. Appl. Log., 10, 368-409, (2012) · Zbl 1285.03049
[14] B. Courcelle, I. Durand, Fly-automata, model-checking and recognizability, Proceedings of the workshop Frontiers of Recognizability, Marseille, 2014, http://arxiv.org/abs/1409.5368. · Zbl 1398.68336
[15] Courcelle, B.; Durand, I., Computations by fly-automata beyond monadic second-order logic, Theoret. Comput. Sci., 619, 32-67, (2016), http://hal.archives-ouvertes.fr/hal-00828211. Short version in Proc. Conference on Algebraic Informatics, Lecture Notes in Comput. Sci. 8080 (2013) 211-222 · Zbl 1335.68116
[16] Courcelle, B.; Engelfriet, J., (Graph Structure and Monadic Second-Order Logic, a Language Theoretic Approach, Encyclopedia of mathematics and its application, vol. 138, (2012), Cambridge University Press)
[17] Courcelle, B.; Heggernes, P.; Meister, D.; Papadopoulos, C.; Rotics, U., A characterisation of clique-width through nested partitions, Discrete Appl. Math., 187, 70-81, (2015) · Zbl 1315.05110
[18] Courcelle, B.; Makowsky, J.; Rotics, U., Linear-time solvable optimization problems on graphs of bounded clique-width, Theory Comput. Syst., 33, 125-150, (2000) · Zbl 1009.68102
[19] Diestel, R., Graph Theory, (2006), Springer
[20] Downey, R.; Fellows, M., Parameterized Complexity, (1999), Springer-Verlag · Zbl 0914.68076
[21] Downey, R.; Fellows, M., Fundamentals of Parameterized Complexity, (2013), Springer-Verlag · Zbl 1358.68006
[22] I. Durand, Object enumeration, in: Proc. of 5th Europeal LISP Conference, Zadar, Croatia, May 2012, pp. 43-57.
[23] Espelage, W.; Gurski, F.; Wanke, E., Deciding clique-width for graphs of bounded tree-width, J. Graph Algorithms Appl., 7, 141-180, (2003) · Zbl 1027.05093
[24] Fellows, M.; Rosamond, F.; Rotics, U.; Szeider, S., Clique-width is NP-complete, SIAM J. Discrete Math., 23, 909-939, (2009) · Zbl 1207.68159
[25] Fischer J. Makowsky, E.; Ravve, E., Counting truth assignments of formulas of bounded tree-width or clique-width, Discrete Appl. Math., 156, 511-529, (2008) · Zbl 1131.68093
[26] Fomin, F.; Oum, S.; Thilikos, D., Rank-width and tree-width of \(H\)-minor-free graphs, European J. Combin., 31, 1617-1628, (2010) · Zbl 1215.05171
[27] Frank, A., Connectivity and networks, (Handbook of Combinatorics, Vol.1, (1997), Elsevier), 111-178
[28] Gurski, F.; Wanke, E., The tree-width of clique-width bounded graphs without \(K_{n, n}\), (Proceedings of 26th Workshop on Graphs (WG), Lecture Notes in Comput. Sci., 1928, (2000)), 196-205 · Zbl 0988.68131
[29] Kolaitis, P.; Vardi, M., Conjunctive-query containment and constraint satisfaction, J. Comput. System Sci., 61, 302-332, (2000) · Zbl 0963.68059
[30] Oum, S., Rank-width is less than or equal to branch-width, J. Graph Theory, 57, 239-244, (2008) · Zbl 1135.05059
[31] Oum, S., Approximating rank-width and clique-width quickly, ACM Trans. Algorithms, 5, 1, (2008) · Zbl 1126.05304
[32] Wood, D., On tree-partition-width, European J. Combin., 30, 1245-1253, (2009) · Zbl 1205.05079
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.