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

DOI10.1016/j.tcs.2015.11.039zbMath1333.68127OpenAlexW2182805349MaRDI QIDQ5899662

Martin Vatshelle, Sigve Hortemo Sæther

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

NP-hardnessBoolean widthbranch decompositionsmaximum induced matching width

Mathematics Subject Classification ID

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

Related Items (17)

Solving problems on generalized convex graphs via mim-width ⋮ Unnamed Item ⋮ Mim-width. I. Induced path problems ⋮ Bounding the mim‐width of hereditary graph classes ⋮ Clique‐width: Harnessing the power of atoms ⋮ Unnamed Item ⋮ On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs ⋮ Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis ⋮ List \(k\)-colouring \(P_t\)-free graphs: a mim-width perspective ⋮ Solving problems on generalized convex graphs via mim-width ⋮ Bounding the Mim-Width of Hereditary Graph Classes. ⋮ Unnamed Item ⋮ Distance Domination in Graphs ⋮ 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 ⋮ Node multiway cut and subset feedback vertex set on graphs of bounded mim-width ⋮ Tractability beyond \(\beta\)-acyclicity for conjunctive queries with negation and SAT

Cites Work

• Unnamed Item
• The parameterized complexity of the induced matching problem
• Induced matchings
• Call routing and the ratcatcher
• Beyond NP-completeness for problems of bounded width (extended abstract)
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• Clique-Width is NP-Complete
• Complexity of Finding Embeddings in a k-Tree
• Approximating rank-width and clique-width quickly
• Parameterized Complexity of Bandwidth on Trees

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