graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, a clique cover or partition into cliques of a given

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

is a partition of the vertices into

cliques A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...

, 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 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 may be seen as a

graph coloring In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices ...

of the

complement graph In the mathematical field of graph theory, the complement or inverse of a graph is a graph on the same vertices such that two distinct vertices of are adjacent if and only if they are not adjacent in . That is, to generate the complement ...

of , the graph on the same vertex set that has edges between non-adjacent vertices of . 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 if and only if it is an independent set in the complement of , so a partition of the vertices of is a clique cover of if and only if it is a coloring of the complement of .

Computational complexity

The clique cover problem in

computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...

is the

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...

ic problem of finding a minimum clique cover, or (rephrased as a

decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...

) finding a clique cover whose number of cliques is below a given threshold. Finding a minimum clique cover is

NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...

, and its

decision version In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whe ...

NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...

. 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.

In special classes of graphs

Perfect graph In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph ( clique number). Equivalently stated in symbolic terms an arbitrary graph G=(V,E) is per ...

s are defined as the graphs in which, for every

induced subgraph In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset. Definit ...

, the chromatic number (minimum number of colors in a coloring) equals 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 In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set S of vertices such that for every two vertices in S, there is no edge connecting the two ...

. It is possible to compute the clique cover number in perfect graphs in

polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

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

triangle-free graph In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with ...

s. In these graphs, every clique cover consists of a matching (a set of disjoint pairs of adjacent vertices) together with

singleton set In mathematics, a singleton, also known as a unit set or one-point set, is a set with exactly one element. For example, the set \ is a singleton whose single element is 0. Properties Within the framework of Zermelo–Fraenkel set theory, t ...

s 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 Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph , and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is ad ...

. The optimum partition into cliques can also be found in polynomial time for graphs of bounded

clique-width In graph theory, the clique-width of a graph is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be bounded even for dense graphs. It is defined as the minimum nu ...

. These include, among other graphs, the

cograph In graph theory, a cograph, or complement-reducible graph, or ''P''4-free graph, is a graph that can be generated from the single-vertex graph ''K''1 by complementation and disjoint union. That is, the family of cographs is the smallest class of ...

s 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 graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cro ...

s and

unit disk graph In geometric graph theory, a unit disk graph is the intersection graph of a family of unit disks in the Euclidean plane. That is, it is a graph with one vertex for each disk in the family, and with an edge between two vertices whenever the corres ...

Approximation

The same

hardness of approximation In computer science, hardness of approximation is a field that studies the algorithmic complexity of finding near-optimal solutions to optimization problems. Scope Hardness of approximation complements the study of approximation algorithms by pro ...

results that are known for graph coloring also apply to clique cover. Therefore, unless

P = NP The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved. The informal term ''quickly'', used above ...

, there can be no

approximation algorithm In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solu ...

for any that, on -vertex graphs, achieves an

approximation ratio An approximation is anything that is intentionally similar but not exactly equal to something else. Etymology and usage The word ''approximation'' is derived from Latin ''approximatus'', from ''proximus'' meaning ''very near'' and the prefix '' ...

better 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

or better. Nevertheless, in

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.. Baker's technique can be used to provide a

polynomial-time approximation scheme In computer science (particularly algorithmics), a polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems). A PTAS is an algorithm which takes an in ...

for the problem on planar graphs.

References

{{reflist Graph theory objects NP-complete problems Computational problems in graph theory

Relation to coloring

Computational complexity

In special classes of graphs

Approximation

Related problems

References