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

absolute approximationclique-widthNP-completenesspathwidth

Mathematics Subject Classification ID

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

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

(32)

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

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)