zbMATH — the first resource for mathematics

Between treewidth and clique-width. (English) Zbl 1409.05201
Kratsch, Dieter (ed.) et al., Graph-theoretic concepts in computer science. 40th international workshop, WG 2014, Nouan-le-Fuzelier, France, June 25–27, 2014. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 8747, 396-407 (2014).
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 the exponential time hypothesis fails, as shown by F. V. Fomin et al. [in: Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 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. The 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 tree-width, 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.
For the entire collection see [Zbl 1318.68028].

05C85 Graph algorithms (graph-theoretic aspects)
05C15 Coloring of graphs and hypergraphs
05C45 Eulerian and Hamiltonian graphs
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI