Polynomial-time recognition of clique-width ≤3 graphs

Abstract : Clique-width is a relatively new parameterization of graphs, philosophically similar to treewidth. Clique-width is more encompassing in the sense that a graph of bounded treewidth is also of bounded clique-width (but not the converse). For graphs of bounded clique-width, given the clique-width decomposition, every optimization, enumeration or evaluation problem that can be defined by a monadic second-order logic formula using quantifiers on vertices, but not on edges, can be solved in polynomial time. This is reminiscent of the situation for graphs of bounded treewidth, where the same statement holds even if quantifiers are also allowed on edges. Thus, graphs of bounded clique-width are a larger class than graphs of bounded treewidth, on which we can resolve fewer, but still many, optimization problems efficiently. One of the major open questions regarding clique-width is whether graphs of clique-width at most k, for fixed k, can be recognized in polynomial time. In this paper, we present the first polynomial-time algorithm (O(n²m)) to recognize graphs of clique-width at most 3.
Complete list of metadatas

https://hal.inria.fr/hal-01274081
Contributor : Michel Habib <>
Submitted on : Monday, February 15, 2016 - 1:35:52 PM
Last modification on : Tuesday, April 2, 2019 - 1:42:25 PM

Links full text

Identifiers

Citation

Derek G. Corneil, Michel Habib, Jean-Marc Lanlignel, Bruce Reed, Udi Rotics. Polynomial-time recognition of clique-width ≤3 graphs. Discrete Applied Mathematics, Elsevier, 2012, Fourth Workshop on Graph Classes, Optimization, and Width Parameters Bergen, Norway, October 2009: Bergen GROW 09, 160 (6), pp.834-865. ⟨10.1016/j.dam.2011.03.020⟩. ⟨hal-01274081⟩

Share

Metrics

Record views

294