Clique-width minimization is NP-hard

DOI10.1145/1132516.1132568MaRDI QIDQ2931399zbMATH OpenOpenAlexWikidataFDO

Authors Michael R. Fellows, Frances Rosamond, Stefan Szeider, 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

zbMATH Keywords

NP-completenesspathwidthclique-widthabsolute approximation

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Clique-width is NP-complete
• scientific article; zbMATH DE number 2044928
• Clique-width: on the price of generality
• Intractability of clique-width parameterizations
• Pathwidth is NP-Hard for Weighted Trees

Cited in

(30)

• Pathwidth is NP-Hard for Weighted Trees
• Hardness of computing width parameters based on branch decompositions over the vertex set
• scientific article; zbMATH DE number 2044928 (Why is no real title available?)
• Minimal classes of graphs of unbounded clique-width
• A new representation of proper interval graphs with an application to clique-width
• Mike Fellows: Weaving the Web of Mathematics and Adventure
• A basic parameterized complexity primer
• On a disparity between relative cliquewidth and relative NLC-width
• Recent developments on graphs of bounded clique-width
• Constrained-path labellings on graphs of bounded clique-width
• Eigenvalue location in graphs of small clique-width
• New Plain-Exponential Time Classes for Graph Homomorphism
• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• Clique-width is NP-complete
• Exploiting Restricted Linear Structure to Cope with the Hardness of Clique-Width
• Line graphs of bounded clique-width
• Graph operations characterizing rank-width
• Locating Eigenvalues of Symmetric Matrices - A Survey
• The relative clique-width of a graph
• U-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
• New plain-exponential time classes for graph homomorphism
• Inductive computations on graphs defined by clique-width expressions
• \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
• Multi-clique-width
• Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width
• Graphs of Linear Clique-Width at Most 3
• Vertex-minor reductions can simulate edge contractions
• The behavior of clique-width under graph operations and graph transformations
• Graph parameters measuring neighbourhoods in graphs-bounds and applications
• Polynomial algorithms for protein similarity search for restricted mRNA structures

This page was built for publication: Clique-width minimization is NP-hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2931399)