CLIQUE DECISION PROBLEM(CDP)
The Clique Problem is a well-known problem in computer science and graph
theory.
Definition of Complete Graph
A graph is called a complete graph if every pair of distinct vertices is
connected by an edge. A complete graph with n vertices is denoted by Kn. In a
complete graph, every possible edge between vertices exists.
.
Here is a complete graph of 5 vertices and every pair of distinct vertices is
connected by an edge. The number of edges in a complete graph is n(n -1)/2,
where n is the number of vertices.
.
Question – Examine the provided graph with 5 vertices. Is this graph
a complete graph, meaning every pair of vertices is connected by an edge?
The vertex 5 is not connected to vertex 3. Hence, it is said that this graph not
a complete graph.
But a subgraph {1, 2, 3, 4} is said to be a complete graph in which all the
pairs are connected by an edge.
A subgraph that forms a complete graph is called a clique. In this case, using
the brute force algorithm, we have identified a 4-clique within the 5-vertex
graph. This means that the subgraph formed by 4 vertices is fully connected,
with every pair of vertices having an edge between them, making it a complete
graph.
We can find that the 4 vertices are fully connected, which means it forms
a maximum clique. This maximum clique includes all four vertices.
Additionally, there are several fully connected 3-vertex combinations, such
as {(1, 2, 3), (2, 3, 4), (1, 2, 4), (1, 3, 4)}. Furthermore, we can identify fully
connected pairs of 2-vertices {(1, 2), (2, 3), (3, 4), (1, 3), (1, 4), (2, 4)}.
.
Classification of Clique Problem
The Clique Problem can be presented in various ways, depending on the
specific cliques and the information needed about them. Common variations of
the problem include
1. Identifying the maximum clique (the largest clique in terms of vertex
count)
2. Finding the maximum weight clique in a weighted graph
3. Listing all maximal cliques
4. The decision problem of determining whether a graph has a clique of
size k.
.
Question – Can you find the maximum clique in the below graph?
Not in the polynomial time, because it is a very very hard problem. Let define
it.
.
Clique Optimization Problem (COP) Statement
Given an undirected graph G = (V, E), the objective of the Clique Optimization
Problem is to find the largest clique in the graph. A clique is a subset of
vertices where every two distinct vertices are connected by an edge. The goal is
to maximize the number of vertices in this fully connected subset.
The Clique Optimization Problem belongs to the class NP-Hard. This means
that while finding the largest clique is difficult (no known polynomial-time
algorithm exists to solve it).
.
Clique Decision Problem (CDP) Statement
Given an undirected graph G = (V, E) and an integer k, the problem is to
determine whether there exists a clique of size k in the graph. In other words,
the task is to decide if there is a subset of k vertices such that every pair of
vertices in this subset is connected by an edge.
This problem asks for a yes or no answer to whether the graph contains a clique
of at least k vertices and is classified as NP-complete.
Reduction from SAT to Clique
The Boolean Satisfiability Problem (SAT) can be polynomially reduced to
the Clique Decision Problem. This means that if we can solve the Clique
Decision Problem efficiently (in polynomial time), then we can also solve 3-
SAT efficiently, implying that the Clique Decision Problem is at least as hard as
3-SAT.
To construct a reduction from the Boolean Satisfiability Problem (3-SAT) to
the Clique Decision Problem, let’s go through an example step-by-step.
.
Algorithm 3-SAT_to_Clique(SAT_formula)
1. Input a Boolean Formula in CNF. The CNF formula consists of m
clauses, each with n literals.
2. Initialize an empty graph G = (V, E). Each literal from each clause in the
formula is represented by a vertex.
3. For each literal in each clause, create a vertex in the graph.
Let vij represent the jth literal in the ith clause.
4. Add edges between two vertices from different clauses if the literals
are not contradictory. Two literals are contradictory if one is the
negation of the other (e.g., x1 and ¬x1).
5. Check for a clique of size m (number of clauses). A clique is a set of
vertices where every pair of vertices is connected by an edge.
6. If G contains a clique of size m
Return True // 3-SAT_formula is satisfiable
Else:
Return False // 3-SAT_formula is unsatisfiable
Example –
Consider the following Boolean formula
F = (x1 ∨ ¬x2 ∨ x3) ∧ (x2 ∨ x3 ∨ ¬x4) ∧ (¬x1 ∨ ¬x3 ∨ x4)
Step 1 – The clauses is 3 and there are 3 literals in each clause.
Step 2 – Create a graph
Step 3 – Add edges between two vertices from different clauses if the literals
are not contradictory.
Step 4 – In this graph, there are many valid cliques of size 3, but I choose the
red colored clique.
If such a clique exists, it means that there is a set of literals, one from each
clause, that are all mutually consistent and satisfy the original SAT formula.
Since 3-SAT can be reduced to the Clique Decision Problem in polynomial
time, the Clique Decision Problem is at least as hard as 3-SAT. Given that 3-
SAT is NP-complete, this shows that the Clique Decision Problem is also
NP-complete.
.
If we can say that SAT can be reduced to Clique Problem, it means
that solving Clique Problem would allow us to solve SAT as well.
Let’s verify from the above example. The clique problem is solved and we need
to solve SAT problem by the vertices of clique.
In the figure, the vertices labelled in red, which form a triangle, represent
specific assignments of the variables –
No x1 means x1 = either True or False. So, we take x1 = false because
of the worst case.
x2 means x2 = True.
x3 means x3 = True.
X4 means x4 = True.
These assignments illustrate how the variables are set to satisfy the constraints
in the problem.
F = (x1 ∨ ¬x2 ∨ x3) ∧ (x2 ∨ x3 ∨ ¬x4) ∧ (¬x1 ∨ ¬x3 ∨ x4)
F = (False V False V True) ∧ (True V True V False) ∧ (True V False V
True)
F = True ∧ True ∧ True
F = True
Hence, SAT Problem is true. it means that solving Clique Problem would
allow us to solve 3-SAT as well.
