zbMATH — the first resource for mathematics

Between treewidth and clique-width. (English) Zbl 1345.05104
Summary: Many hard graph problems can be solved efficiently when restricted to graphs of bounded treewidth, and more generally to graphs of bounded clique-width. But there is a price to be paid for this generality, exemplified by the four problems MaxCut, graph coloring, Hamiltonian cycle and edge dominating set that are all FPT parameterized by treewidth but none of which can be FPT parameterized by clique-width unless FPT = W[1], as shown by F. Fomin et al. [in: Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, TX, USA, January 17–19, 2010. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). New York, NY: Association for Computing Machinery (ACM). 493–502 (2010; Zbl 1288.05269)]. We therefore seek a structural graph parameter that shares some of the generality of clique-width without paying this price. Based on splits, branch decompositions and the work of M. Vatshelle [New width parameters of graphs. Bergen: University of Bergen (PhD Thesis) (2012)] on maximum matching-width, we consider the graph parameter \(sm\)-width which lies between treewidth and clique-width. Some graph classes of unbounded treewidth, like distance-hereditary graphs, have bounded sm-width. We show that MaxCut, graph coloring, Hamiltonian cycle and edge dominating set are all FPT parameterized by \(sm\)-width.

05C85 Graph algorithms (graph-theoretic aspects)
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Full Text: DOI
[1] Arnborg, S, Efficient algorithms for combinatorial problems on graphs with bounded decomposabilitya survey, BIT Numer. Math., 25, 1-23, (1985) · Zbl 0573.68018
[2] Bui-Xuan, B-M; Telle, JA; Vatshelle, M, Boolean-width of graphs, Theor. Comput. Sci., 412, 5187-5204, (2011) · Zbl 1225.68133
[3] Charbit, P; Montgolfier, F; Raffinot, M, Linear time split decomposition revisited, SIAM J. Discrete Math., 26, 499-514, (2012) · Zbl 1248.68369
[4] Corneil, DG; Rotics, U, On the relationship between clique-width and treewidth, SIAM J. Comput., 34, 825-847, (2005) · Zbl 1069.05067
[5] 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
[6] Courcelle, B, The monadic second-order logic of graphs. I. recognizable sets of finite graphs, Inf. Comput., 85, 12-75, (1990) · Zbl 0722.03008
[7] Cunningham, WH, Decomposition of directed graphs, SIAM J. Algebr. Discrete Methods, 3, 214-228, (1982) · Zbl 0497.05031
[8] Fomin, F., Golovach, P., Lokshtanov, D., Saurabh, S.: Algorithmic lower bounds for problems parameterized by clique-width. In: Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pp. 493-502. (2010a) · Zbl 1288.05269
[9] Fomin, F., Golovach, P., Lokshtanov, D., Saurabh, S.: Intractability of clique-width parameterizations. SIAM J. Comput. 39(5), 1941-1956 (2010b) · Zbl 1207.68161
[10] Gajarský, J., Lampis, M., Ordyniak, S.: Parameterized algorithms for modular-width. In: Parameterized and Exact Computation, pp. 163-176. Springer, Berlin (2013) · Zbl 1406.68080
[11] Ganian, R.: Twin-cover: beyond vertex cover in parameterized algorithmics. In: Parameterized and Exact Computation, pp. 259-271. Springer, Berlin (2011) · Zbl 1352.68105
[12] Ganian, R., Hliněnỳ, P., Nešetřil, J., Obdržálek, J., de Mendez, P.O., Ramadurai, R.: When trees grow low: shrubs and fast mso1. In: Mathematical Foundations of Computer Science 2012, pp. 419-430. Springer, Berlin (2012)
[13] Hliněnỳ, P; Oum, S; Seese, D; Gottlob, G, Width parameters beyond tree-width and their applications, Comput. J., 51, 326-362, (2008)
[14] Kreutzer, S., Tazari, S.: Lower bounds for the complexity of monadic second-order logic. In: Logic in Computer Science (LICS), 2010 25th Annual IEEE Symposium on, pp. 189-198. IEEE Computer Society, Silver Spring, MD (2010) · Zbl 1288.05282
[15] Lampis, M, Algorithmic meta-theorems for restrictions of treewidth, Algorithmica, 64, 19-37, (2012) · Zbl 1252.68154
[16] Oum, S, Rank-width and vertex-minors, J. Comb. Theory, Ser. B, 95, 79-100, (2005) · Zbl 1070.05023
[17] Oum, S; Seymour, P, Approximating clique-width and branch-width, J. Comb. Theory, Ser. B, 96, 514-528, (2006) · Zbl 1114.05022
[18] Rao, Michaël, Solving some NP-complete problems using split decomposition, Discrete Appl. Math., 156, 2768-2780, (2008) · Zbl 1155.05058
[19] Robertson, Neil; Seymour, Paul D, Graph minors. X. obstructions to tree-decomposition, J. Comb. Theory, Ser. B, 52, 153-190, (1991) · Zbl 0764.05069
[20] Sæther, S.H.: Solving hamiltonian cycle by an EPT algorithm for a non-sparse parameter. In: Algorithms and Discrete Applied Mathematics, pp. 205-216. Springer, Berlin (2015) · Zbl 1432.68196
[21] Vatshelle, M.: New width parameters of graphs. PhD thesis, The University of Bergen, (2012) · Zbl 1114.05022
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.