11.7. The Clique Problem¶

11.7.1. The Clique Problem¶

CLIQUE PROBLEM

1 / 12 Settings

<<<>>>

Introduction to the Clique problem

This slideshow introduces and explains the "Clique" Problem.

We start with some definitions and background.

If in a graph

$G$ there exists a complete subgraph of

$k$ nodes,

$G$ is said to contain a

$k$ -clique.

For example, the following graph contains a

$3$ -clique. (Actually, there is more than one.)

Any clique with the largest number of vertices in a graph

$G$ is called a Maximum Clique in

$G$ .

For example, the Maximum Clique in this graph is a

$4$ -clique.

The Clique Problem can be defined as either of the following:

Given a graph $G = (V , E)$ , find the Maximum Clique in $G$ . This is the optimization form of the problem.

Or

Given a graph $G = (V, E)$ , and a number $k$ , does $G$ contain a Clique of size $\geq k$ ? This is the decision form of the problem.

In the graph below does there exist a clique of size

$\geq 5$ ?

In the graph below does there exist a clique of size

$\geq 4$ ?

Saving...

Server Error
Resubmit

Try out an instance of the Clique problem on your own.

Formal Languages With Visualizations

Chapter 11 Limits to Computing

11.7. The Clique Problem¶

11.7.1. The Clique Problem¶