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

DOI10.1016/J.ENDM.2015.06.041MaRDI QIDQ5890909zbMATH OpenOpenAlexFDO

Authors Sigve Hortemo Sæther, Martin Vatshelle

Publication date 14 October 2016

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2015.06.041

zbMATH Keywords

Boolean widthbranch decompositioncomplexitycut functionmim-width

Mathematics Subject Classification ID

Distance in graphs (05C12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) 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
• Boolean-width of graphs
• Between treewidth and clique-width
• Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis

Cites work

• Approximating rank-width and clique-width quickly
• 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
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The parameterized complexity of the induced matching problem
• Upper Bounds on Boolean-Width with Applications to Exact Algorithms

Cited in

(4)

• Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis
• Computability of width of submodular partition functions
• Hardness of computing width parameters based on branch decompositions over the vertex set
• Mim-width is paraNP-complete

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 Q5890909)