Clique-Width is NP-Complete
From MaRDI portal
Publication:3563951
DOI10.1137/070687256zbMath1207.68159OpenAlexW2015142920WikidataQ56456200 ScholiaQ56456200MaRDI QIDQ3563951
Stefan Szeider, Frances A. Rosamond, Michael R. Fellows, Udi Rotics
Publication date: 1 June 2010
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/92fb456bfe2f1f9f7f7445a1c24f0ee53b7e264b
Structural characterization of families of graphs (05C75) Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (56)
Clique-width of path powers ⋮ Iterated Type Partitions ⋮ Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width ⋮ Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics ⋮ A Basic Parameterized Complexity Primer ⋮ Vertex-minors, monadic second-order logic, and a conjecture by Seese ⋮ The rank-width of edge-coloured graphs ⋮ Grammars and clique-width bounds from split decompositions ⋮ On quasi-planar graphs: clique-width and logical description ⋮ Tight complexity bounds for FPT subgraph problems parameterized by the clique-width ⋮ From tree-decompositions to clique-width terms ⋮ Bounding the Clique-Width of H-free Chordal Graphs ⋮ A SAT Approach to Clique-Width ⋮ Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs ⋮ Between clique-width and linear clique-width of bipartite graphs ⋮ On the computational difficulty of the terminal connection problem ⋮ Fair allocation algorithms for indivisible items under structured conflict constraints ⋮ Graph classes with and without powers of bounded clique-width ⋮ Bounding clique-width via perfect graphs ⋮ Polynomial-time recognition of clique-width \(\leq 3\) graphs ⋮ On the model-checking of monadic second-order formulas with edge set quantifications ⋮ Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs ⋮ Stability, vertex stability, and unfrozenness for special graph classes ⋮ Unnamed Item ⋮ Clique-Width for Graph Classes Closed under Complementation ⋮ Three remarks on \(\mathbf{W}_{\mathbf{2}}\) graphs ⋮ Directed NLC-width ⋮ Automata for the verification of monadic second-order graph properties ⋮ Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis ⋮ Finer Tight Bounds for Coloring on Clique-Width ⋮ Hardness of computing width parameters based on branch decompositions over the vertex set ⋮ Clique-width with an inactive label ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Hardness of computing width parameters based on branch decompositions over the vertex set ⋮ Complexity of conflict-free colorings of graphs ⋮ Computing the Clique-Width of Large Path Powers in Linear Time via a New Characterisation of Clique-Width ⋮ Neighbourhood-width of trees ⋮ Polynomial-time algorithm for isomorphism of graphs with clique-width at most three ⋮ The behavior of clique-width under graph operations and graph transformations ⋮ Unnamed Item ⋮ Graphs of linear clique-width at most 3 ⋮ Letter graphs and geometric grid classes of permutations: characterization and recognition ⋮ Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity ⋮ Alliances in graphs of bounded clique-width ⋮ Bounding Clique-Width via Perfect Graphs ⋮ Computations by fly-automata beyond monadic second-order logic ⋮ An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width ⋮ Unnamed Item ⋮ Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs ⋮ \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited ⋮ Comparing linear width parameters for directed graphs ⋮ Optimal centrality computations within bounded clique-width graphs ⋮ Clique-width of full bubble model graphs ⋮ Finding Branch-Decompositions of Matroids, Hypergraphs, and More ⋮ Linear rank-width and linear clique-width of trees ⋮ A characterisation of clique-width through nested partitions
This page was built for publication: Clique-Width is NP-Complete
