Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis

DOI10.3390/a11110173zbMath1461.68169OpenAlexW2899349648MaRDI QIDQ1712018

Koichi Yamazaki

Publication date: 21 January 2019

Published in: Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3390/a11110173

zbMATH Keywords

inapproximabilitygraph-width parametersmall set expansion hypothesis

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (2)

Distance Domination in Graphs ⋮ Node multiway cut and subset feedback vertex set on graphs of bounded mim-width

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Constant-degree graph expansions that preserve treewidth
• Girth and treewidth
• Boolean-width of graphs
• The NLC-width and clique-width for powers of graphs of bounded tree-width
• A partial k-arboretum of graphs with bounded treewidth
• Call routing and the ratcatcher
• \(k\)-NLC graphs and polynomial algorithms
• Upper bounds to the clique width of graphs
• Square roots of minor closed graph classes
• Approximating the path-distance-width for AT-free graphs and graphs in related classes
• Line graphs of bounded clique-width
• Parametrized complexity theory.
• Approximating clique-width and branch-width
• The carvingwidth of hypercubes
• Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis
• The point-set embeddability problem for plane graphs
• Graph expansion and the unique games conjecture
• Rank-width of random graphs
• On the Boolean-Width of a Graph: Structure and Applications
• Subexponential Algorithms for Unique Games and Related Problems
• Clique-Width is NP-Complete
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds
• Approximating rank-width and clique-width quickly
• Inapproximability of Treewidth and Related Problems
• Rank‐width is less than or equal to branch‐width
• The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ ₁
• Parameterized Algorithms
• Hardness of computing width parameters based on branch decompositions over the vertex set
• On approximation intractability of the path-distance-width problem

This page was built for publication: Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis