Clique-Width is NP-Complete
From MaRDI portal
Publication:3563951
DOI10.1137/070687256zbMath1207.68159WikidataQ56456200 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
05C75: Structural characterization of families of graphs
68Q42: Grammars and rewriting systems
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Unnamed Item, Unnamed Item, Unnamed Item, Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs, Finding Branch-Decompositions of Matroids, Hypergraphs, and More, Iterated Type Partitions, Clique-Width for Graph Classes Closed under Complementation, Finer Tight Bounds for Coloring on Clique-Width, Hardness of computing width parameters based on branch decompositions over the vertex set, Hardness of computing width parameters based on branch decompositions over the vertex set, Letter graphs and geometric grid classes of permutations: characterization and recognition, Computations by fly-automata beyond monadic second-order logic, An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width, On the computational difficulty of the terminal connection problem, Fair allocation algorithms for indivisible items under structured conflict constraints, Stability, vertex stability, and unfrozenness for special graph classes, Three remarks on \(\mathbf{W}_{\mathbf{2}}\) graphs, Clique-width of path powers, Tight complexity bounds for FPT subgraph problems parameterized by the clique-width, 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, Clique-width with an inactive label, Practical algorithms for MSO model-checking on tree-decomposable graphs, Complexity of conflict-free colorings of graphs, Neighbourhood-width of trees, The behavior of clique-width under graph operations and graph transformations, Graphs of linear clique-width at most 3, Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity, Vertex-minors, monadic second-order logic, and a conjecture by Seese, Graph classes with and without powers of bounded clique-width, Directed NLC-width, Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis, Automata for the verification of monadic second-order graph properties, Polynomial-time algorithm for isomorphism of graphs with clique-width at most three, Alliances in graphs of bounded clique-width, \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited, Optimal centrality computations within bounded clique-width graphs, Grammars and clique-width bounds from split decompositions, On quasi-planar graphs: clique-width and logical description, Between clique-width and linear clique-width of bipartite graphs, Comparing linear width parameters for directed graphs, Clique-width of full bubble model graphs, Linear rank-width and linear clique-width of trees, A characterisation of clique-width through nested partitions, The rank-width of edge-coloured graphs, From tree-decompositions to clique-width terms, Bounding clique-width via perfect graphs, Bounding Clique-Width via Perfect Graphs, Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width, Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics, A Basic Parameterized Complexity Primer, 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, Computing the Clique-Width of Large Path Powers in Linear Time via a New Characterisation of Clique-Width
