Clique cover

Source: Wikipedia, the free encyclopedia.

In

undirected graph is a partition of the vertices into cliques
, subsets of vertices within which every two vertices are adjacent. A minimum clique cover is a clique cover that uses as few cliques as possible. The minimum k for which a clique cover exists is called the clique cover number of the given graph.

Relation to coloring

A clique cover of a graph G may be seen as a graph coloring of the complement graph of G, the graph on the same vertex set that has edges between non-adjacent vertices of G. Like clique covers, graph colorings are partitions of the set of vertices, but into subsets with no adjacencies (independent sets) rather than cliques. A subset of vertices is a clique in G if and only if it is an independent set in the complement of G, so a partition of the vertices of G is a clique cover of G if and only if it is a coloring of the complement of G.

Computational complexity

The clique cover problem in

NP-complete. It was one of Richard Karp's original 21 problems shown NP-complete in his 1972 paper "Reducibility Among Combinatorial Problems".[1]

The equivalence between clique covers and coloring is a reduction that can be used to prove the NP-completeness of the clique cover problem from the known NP-completeness of graph coloring.[2]

In special classes of graphs

maximum clique
. According to the
polynomial time
.

Another class of graphs in which the minimum clique cover can be found in polynomial time are the

maximum matching
.

The optimum partition into cliques can also be found in polynomial time for graphs of bounded clique-width.[3] These include, among other graphs, the cographs and distance-hereditary graphs, which are both also classes of perfect graphs.

The clique cover problem remains NP-complete on some other special classes of graphs, including the cubic planar graphs[4] and unit disk graphs.[5]

Approximation

The same

approximation ratio better than n1 − ε.[6]

In graphs where every vertex has

polynomial time it is possible to find an approximation with ratio 5/4. That is, this approximation algorithm finds a clique cover whose number of cliques is no more than 5/4 times the optimum.[4]

Baker's technique can be used to provide a polynomial-time approximation scheme for the problem on planar graphs.[7]

Related problems

The related

clique edge cover problem concerns partitioning the edges of a graph, rather than the vertices, into subgraphs induced by cliques. It is also NP-complete.[8]

References

  1. Karp, Richard (1972), "Reducibility Among Combinatorial Problems" (PDF), in Miller, R. E.; Thatcher, J. W. (eds.), Proceedings of a Symposium on the Complexity of Computer Computations, Plenum Press, pp. 85–103, archived from the original
    (PDF) on 2011-06-29, retrieved 2008-08-29
  2. ISBN 0-7167-1045-5
    A1.2: GT19, pg.194.
  3. doi:10.1007/3-540-45477-2_12
    .
  4. ^
    doi:10.1016/j.dam.2007.10.015
    .
  5. arXiv:0909.1552 [cs.CG
    ].
  6. doi:10.4086/toc.2007.v003a006
    .
  7. doi:10.1137/1.9781611972924.10
  8. ^ Garey & Johnson (1979), Problem GT59.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Clique_cover&oldid=1096498928"