Clique Decision Problem (CDP)
The Clique Decision Problem (CDP) is a classic problem in graph theory and computational complexity. It
involves determining whether a given graph contains a clique of a specified size.
Problem Definition
- Input:
1. An undirected graph G = (V, E), where V is the set of vertices and E is the set of edges.
2. An integer k, representing the size of the clique.
- Output:
- True if G contains a clique of size k .
- False otherwise.
What is a Clique?
A clique in a graph is a subset of vertices such that every two distinct vertices in the subset are
connected by an edge. In other words, it is a complete subgraph.
Example
# Input:
1. Graph G :
- Vertices V = A, B, C, D, E .
- Edges E = (A, B), (A, C), (B, C), (B, D), (C, D), (D, E) .
2. k = 3 (we are looking for a clique of size 3).
GENERAL Question Asked: Does G contain a clique of size k = 3?
# Step-by-Step Solution:
1. Graph Representation:
The graph can be visualized as:
```
A --- B
\ /
C --- D
```
2. Find All Subsets of Size 3:
- Subsets of vertices of size 3: {A, B, C}, {A, B, D}, {A, C, D}, {B, C, D}……. ,
3. Check for Cliques:
- A subset of vertices forms a clique if there is an edge between every pair of vertices in the subset.
- Check:
- A, B, C : Edges (A, B), (A, C), (B, C) exist. This is a clique.
- B, C, D : Edges (B, C), (C, D), (B, D) exist. This is a clique.
- Other subsets do not satisfy the clique condition.
4. Conclusion:
- G contains a clique of size k = 3 .
# Output:
- True, G has a clique of size 3.
Applications of CDP
1. Social Network Analysis:
- Identifying tightly-knit groups of individuals in social networks.
2. Bioinformatics:
- Finding protein interaction networks.
3. Complexity Theory:
- Used to study NP-completeness (CDP is NP-complete).
4. Optimization Problems:
- Solving scheduling and clustering problems.
CDP and NP-Completeness
The Clique Decision Problem is NP-complete, meaning:
1. It belongs to the class NP (a solution can be verified in polynomial time).
2. Any other NP problem can be reduced to CDP in polynomial time.
