Clique-width minimization is NP-hard
From MaRDI portal
Publication:2931399
DOI10.1145/1132516.1132568zbMath1301.68145OpenAlexW2019880676MaRDI QIDQ2931399
Michael R. Fellows, Stefan Szeider, Frances A. Rosamond, Udi Rotics
Publication date: 25 November 2014
Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1132516.1132568
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (24)
Eigenvalue location in graphs of small clique-width ⋮ Polynomial algorithms for protein similarity search for restricted mRNA structures ⋮ Mike Fellows: Weaving the Web of Mathematics and Adventure ⋮ A Basic Parameterized Complexity Primer ⋮ The relative clique-width of a graph ⋮ Vertex-minors, monadic second-order logic, and a conjecture by Seese ⋮ Inductive computations on graphs defined by clique-width expressions ⋮ Graphs of Linear Clique-Width at Most 3 ⋮ Locating Eigenvalues of Symmetric Matrices - A Survey ⋮ New plain-exponential time classes for graph homomorphism ⋮ Constrained-path labellings on graphs of bounded clique-width ⋮ Minimal classes of graphs of unbounded clique-width ⋮ Vertex-minor reductions can simulate edge contractions ⋮ Line graphs of bounded clique-width ⋮ Graph parameters measuring neighbourhoods in graphs-bounds and applications ⋮ Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width ⋮ Recent developments on graphs of bounded clique-width ⋮ On a disparity between relative cliquewidth and relative NLC-width ⋮ Unnamed Item ⋮ New Plain-Exponential Time Classes for Graph Homomorphism ⋮ Graph operations characterizing rank-width ⋮ \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited ⋮ A new representation of proper interval graphs with an application to clique-width ⋮ Unnamed Item
This page was built for publication: Clique-width minimization is NP-hard
