Hardness of computing width parameters based on branch decompositions over the vertex set

DOI10.1016/J.TCS.2015.11.039MaRDI QIDQ5899662zbMATH OpenOpenAlexFDO

Authors Sigve Hortemo Sæther, Martin Vatshelle

Publication date 21 January 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.11.039

zbMATH Keywords

Boolean widthbranch decompositionsmaximum induced matching widthNP-hardness

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Hardness of computing width parameters based on branch decompositions over the vertex set
• Computing rank-width exactly
• Clique-width minimization is NP-hard
• Boolean-width of graphs
• Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis

Cites work

• Approximating rank-width and clique-width quickly
• Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
• Call routing and the ratcatcher
• Clique-width is NP-complete
• Complexity of Finding Embeddings in a k-Tree
• Induced matchings
• On the approximability of the maximum feasible subsystem problem with 0/1-coefficients
• Parameterized complexity of bandwidth on trees
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The parameterized complexity of the induced matching problem

Cited in

(21)

• Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis
• Tractability beyond -acyclicity for conjunctive queries with negation and SAT
• Mim-width. I. Induced path problems
• List k-colouring P_t-free graphs: a mim-width perspective
• Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
• Mim-width. III. Graph powers and generalized distance domination problems
• On algorithmic applications of sim-width and mim-width of (H₁,H₂)-free graphs
• A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width
• Distance domination in graphs
• Generalized distance domination problems and their complexity on graphs of bounded mim-width
• Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-width
• Hardness of computing width parameters based on branch decompositions over the vertex set
• Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
• Bounding the mim‐width of hereditary graph classes
• Clique‐width: Harnessing the power of atoms
• Bounding the Mim-Width of Hereditary Graph Classes.
• Solving problems on generalized convex graphs via mim-width
• Finding induced subgraphs from graphs with small mim-width
• Comparing width parameters on graph classes
• Mim-width is paraNP-complete
• Solving problems on generalized convex graphs via mim-width

This page was built for publication: Hardness of computing width parameters based on branch decompositions over the vertex set

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