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

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