Between treewidth and clique-width

DOI10.1007/978-3-319-12340-0_33zbMATH Open1409.05201arXiv1404.7758OpenAlexW2125561319MaRDI QIDQ2945207FDOQ2945207

Authors: Sigve Hortemo Sæther, Jan Arne Telle 

Publication date: 9 September 2015

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Abstract: 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 Fomin et al [7, 8]. 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 Vatshelle [18] 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.

Full work available at URL: https://arxiv.org/abs/1404.7758

Recommendations

• Between treewidth and clique-width
• Clique-width: on the price of generality
• Algorithmic lower bounds for problems parameterized by clique-width
• Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
• Intractability of clique-width parameterizations

zbMATH Keywords

Hamiltonian cyclegraph coloringMaxCutedge dominating set

Mathematics Subject Classification ID

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

Cites Work

• Graph minors. X: Obstructions to tree-decomposition
• Algorithmic meta-theorems for restrictions of treewidth
• Linear time solvable optimization problems on graphs of bounded clique-width
• Approximating clique-width and branch-width
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• On the Relationship Between Clique-Width and Treewidth
• When trees grow low: shrubs and fast \(\mathrm{MSO}_{1}\)
• Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
• Parameterized Algorithms for Modular-Width
• Linear time split decomposition revisited
• Decomposition of Directed Graphs
• Algorithmic lower bounds for problems parameterized by clique-width
• Boolean-width of graphs
• Solving some NP-complete problems using split decomposition
• Between treewidth and clique-width

Cited In (11)

• Structural parameterizations of budgeted graph coloring
• Between treewidth and clique-width
• Parameterized compilation lower bounds for restricted CNF-formulas
• Clique-width: on the price of generality
• Edge-treewidth: algorithmic and combinatorial properties
• Maximum matching width: new characterizations and a fast algorithm for dominating set
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• Multi-clique-width
• Solving Hamiltonian cycle by an EPT algorithm for a non-sparse parameter
• Solving Hamiltonian cycle by an EPT algorithm for a non-sparse parameter
• Between treewidth and clique-width

This page was built for publication: Between treewidth and clique-width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2945207)