Parameter: cliquewidth

Definition:

The cliquewidth of a graph is the number of different labels that is needed to construct the graph using the following operations:

References

[1174]
B. Courcelle, S. Olariu
Upper bounds to the clique-width of graphs.
Discrete Appl. Math. 101 (2000) 77-114

Equivalent parameters

Only references for direct inclusions are given. Where no reference is given for an equivalent parameter, check other equivalent parameters.

Relations

Minimal/maximal is with respect to the contents of ISGCI. Only references for direct bounds are given. Where no reference is given, check equivalent parameters.

Minimal upper bounds for this parameter

Problems

Problems in italics have no summary page and are only listed when ISGCI contains a result for the current parameter.

3-Colourability
[?]
Input: A graph G in this class.
Output: True iff each vertex of G can be assigned one colour out of 3 such that whenever two vertices are adjacent, they have different colours.
FPT-Linear
FPT from FPT-Linear on cliquewidth
FPT-Linear
Clique
[?]
Input: A graph G in this class and an integer k.
Output: True iff G contains a set S of pairwise adjacent vertices, with |S| >= k.
FPT
FPT
Clique cover
[?]
Input: A graph G in this class and an integer k.
Output: True iff the vertices of G can be partitioned into k sets Si, such that whenever two vertices are in the same set Si, they are adjacent.
XP
XP
[1714]
W. Espelage, F. Gurski, E. Wanke
How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time
Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science WG'01, LNCS 2204, 117-128 (2001)

Colourability
[?]
Input: A graph G in this class and an integer k.
Output: True iff each vertex of G can be assigned one colour out of k such that whenever two vertices are adjacent, they have different colours.
FPT
FPT
Domination
[?]
Input: A graph G in this class and an integer k.
Output: True iff G contains a set S of vertices, with |S| <= k, such that every vertex in G is either in S or adjacent to a vertex in S.
FPT-Linear
FPT from FPT-Linear on cliquewidth
FPT-Linear
[1701]
M. Vatshelle
New Width Parameters of Graphs
PhD Thesis, Dept. of Informatics, University of Bergen 2012

FPT on booleanwidth
[1701]
M. Vatshelle
New Width Parameters of Graphs
PhD Thesis, Dept. of Informatics, University of Bergen 2012

Feedback vertex set
[?]
Input: A graph G in this class and an integer k.
Output: True iff G contains a set S of vertices, with |S| <= k, such that every cycle in G contains a vertex from S.
FPT
FPT
Graph isomorphism
[?]
Input: Graphs G and H in this class
Output: True iff G and H are isomorphic.
XP
XP on rankwidth
[1763]
M. Grohe, P. Schweitzer
Isomorphism Testing for Graphs of Bounded Rank Width
Proc. of 55th Annual IEEE Symposium on Foundations of Computer Science FOCS (2015)

Hamiltonian cycle
[?]
Input: A graph G in this class.
Output: True iff G has a simple cycle that goes through every vertex of the graph.
XP
XP
[1714]
W. Espelage, F. Gurski, E. Wanke
How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time
Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science WG'01, LNCS 2204, 117-128 (2001)
[1715]
R. Ganian, P. Hlineny, J. Obdrzalek
Clique-width: When hard does not mean impossible
Symposium on Theoretical Aspects of Computer Science STACS 2011, Leibniz International Proceedings in Informatics LIPIcs Vol 9, Dagstuhl 404-415 (2011)

Hamiltonian path
[?]
Input: A graph G in this class.
Output: True iff G has a simple path that goes through every vertex of the graph.
XP
XP
[1714]
W. Espelage, F. Gurski, E. Wanke
How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time
Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science WG'01, LNCS 2204, 117-128 (2001)
[1715]
R. Ganian, P. Hlineny, J. Obdrzalek
Clique-width: When hard does not mean impossible
Symposium on Theoretical Aspects of Computer Science STACS 2011, Leibniz International Proceedings in Informatics LIPIcs Vol 9, Dagstuhl 404-415 (2011)

XP on rankwidth
[1701]
M. Vatshelle
New Width Parameters of Graphs
PhD Thesis, Dept. of Informatics, University of Bergen 2012

Independent set
[?]
Input: A graph G in this class and an integer k.
Output: True iff G contains a set S of pairwise non-adjacent vertices, such that |S| >= k.
FPT
FPT
[1716]
F. Gurski
A comparison of two approaches for polynomial time algorithms computing basic graph parameters
Manuscript 2008

Maximum cut
[?]
(decision variant)
Input: A graph G in this class and an integer k.
Output: True iff the vertices of G can be partitioned into two sets A,B such that there are at least k edges in G with one endpoint in A and the other endpoint in B.
XP,W-hard
XP
[1735]
E. Wanke
k-NLC graphs and polynomial algorithsm
Discrete Appl. Math. 54 No.2 251-266 (1994)

W-hard
[1736]
F.V. Fomin, P.A. Golovach, D. Lokshtanov, S. Saurabh
Almost optimal lower bounds for problems parametrized by clique-width
SIAM J. Comput. 43 No.5 1541-1563 (2014)

Monopolarity
[?]
Input: A graph G in this class.
Output: True iff G is monopolar.
Unknown to ISGCI
Polarity
[?]
Input: A graph G in this class.
Output: True iff G is polar.
XP
XP
[1764]
V.B. Le, R. Nevries
Complexity and algorithms for recognizing polar and monopolar graphs
Theoretical Computer Science 528 1-11 (2014)

Weighted clique
[?]
Input: A graph G in this class with weight function on the vertices and a real k.
Output: True iff G contains a set S of pairwise adjacent vertices, such that the sum of the weights of the vertices in S is at least k.
FPT
FPT
Weighted feedback vertex set
[?]
Input: A graph G in this class with weight function on the vertices and a real k.
Output: True iff G contains a set S of vertices, such that the sum of the weights of the vertices in S is at most k and every cycle in G contains a vertex from S.
FPT-Linear
FPT from FPT-Linear on cliquewidth
FPT-Linear
FPT on rankwidth
[1701]
M. Vatshelle
New Width Parameters of Graphs
PhD Thesis, Dept. of Informatics, University of Bergen 2012

Weighted independent dominating set
[?]
Input: A graph G in this class with weight function on the vertices and a real k.
Output: True iff G contains a set S of pairwise non-adjacent vertices, with the sum of the weights of the vertices in S at most k, such that every vertex in G is either in S or adjacent to a vertex in S.
FPT-Linear
FPT from FPT-Linear on cliquewidth
FPT-Linear
Weighted independent set
[?]
Input: A graph G in this class with weight function on the vertices and a real k.
Output: True iff G contains a set S of pairwise non-adjacent vertices, such that the sum of the weights of the vertices in S is at least k.
FPT-Linear
FPT from FPT-Linear on cliquewidth
FPT-Linear
[1701]
M. Vatshelle
New Width Parameters of Graphs
PhD Thesis, Dept. of Informatics, University of Bergen 2012

FPT on booleanwidth
[1701]
M. Vatshelle
New Width Parameters of Graphs
PhD Thesis, Dept. of Informatics, University of Bergen 2012

Graph classes

Bounded

back to top

Unbounded

back to top

Open

back to top

Unknown to ISGCI

back to top

AltStyle によって変換されたページ (->オリジナル) /