In graph theory, a clique cover or partition into cliques of a given undirected graph is a partition of the vertices of the graph 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 rather than cliques. A subset of vertices is a clique in Gif 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.
The clique cover problem in computational complexity theory is the algorithmic problem of finding a minimum clique cover, or finding a clique cover whose number of cliques is below a given threshold. Finding a minimum clique cover is NP-hard, and its decision version is NP-complete. It was one of Richard Karp's original 21 problems shown NP-complete in his 1972 paper "Reducibility Among Combinatorial Problems". 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.
s are defined as the graphs in which, for every induced subgraph, the chromatic numberequals the size of the maximum clique. According to the weak perfect graph theorem, the complement of a perfect graph is also perfect. Therefore, the perfect graphs are also the graphs in which, for every induced subgraph, the clique cover number equals the size of the maximum independent set. It is possible to compute the clique cover number in perfect graphs in polynomial time. Another class of graphs in which the minimum clique cover can be found in polynomial time are the triangle-free graphs. In these graphs, every clique cover consists of a matching together with singleton sets for the remaining unmatched vertices. The number of cliques equals the number of vertices minus the number of matched pairs. Therefore, in triangle-free graphs, the minimum clique cover can be found by using an algorithm for maximum matching. The optimum partition into cliques can also be found in polynomial time for graphs of bounded clique-width. These include, among other graphs, the cographs and distance-hereditary graphs, which are both also classes of perfect graphs.
Approximation
The same hardness of approximation results that are known for graph coloring also apply to clique cover. Therefore, unless P = NP, there can be no polynomial time approximation algorithm for any that, on -vertex graphs, achieves an approximation ratiobetter than. In graphs where every vertex has at most three neighbors, the clique cover remains NP-hard, and there is a constant such that it is NP-hard to approximate with approximation ratio or better. Nevertheless, in 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.
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.
