Skip to content

Clique

A subset of vertices \(S\) in a graph \(G = (V, E)\) is a clique if every distinct pair of vertices of \(S\) is connected.

A maximum clique is an clique of largest possible size. This size is called the clique number of \(G\) and is usually denoted by \(\omega(G)\).

A clique clover or partition into cliques is a partition of the vertices of the graph into cliques.

A minimum clique cover is a clique cover with the smallest possible number of cliques. This number is called the clique cover number of the graph.

Clique search and decision problem

The clique decision problem consists in deciding whether a graph, given a natural integer \(k\), has a clique of size \(k\). This problem has been proven to be NP-complete (Karp, 1972) [1]. The clique search problem consists in finding such a clique.

Finding a clique of size \(k\) is equivalent to finding an independent set of size \(k\) in the graph's complement.

Maximum clique problem and clique number

The maximum clique problem consists in finding a maximum clique in the graph; it is NP-hard.

Finding a maximum clique is equivalent to finding a maximum independent set in the graph's complement.

Computing the clique number of a graph is also NP-hard. It is equal to the independence number of the graph's complement.

Clique cover search and decision problem

The clique cover decision problem consists in deciding whether a graph, given a natural integer \(k\), has a clique cover of size \(k\). This problem has been proven to be NP-complete (Karp, 1972) [1].The clique cover search problem consists in finding such a clique.

Finding a clique cover of size \(k\) is equivalent to finding a k-coloring in the graph's complement.

Minimum clique cover problem and clique cover number

The minimum clique cover problem consists in finding a minimum clique cover in the graph; it is NP-hard.

Finding a mininum clique cover is equivalent to finding a minimum coloring in the graph's complement.

Computing the clique cover number of a graph is also NP-hard. It is equal to the chromatic number of the graph's complement.

[1] Karp, Richard M., “Reducibility Among Combinatorial Problems”. Complexity of Computer Computations, 1972: Plenum Press, 85-103.