Two Clique Problem
Problem Statement
Given an undirected graph, determine if its vertices can be partitioned into two cliques. A clique is a subset of vertices where every pair is connected by an edge. In other words, can we split all vertices into two groups where each group forms a complete subgraph?
Example:
- Input:
V = 5, edges = [(0,1),(0,2),(0,3),(1,2),(1,3),(2,3),(3,4)] - Output:
true(Clique 1: 3, Clique 2: 4)
Noob-Friendly Explanation
Imagine a school class. You want to divide all students into two groups. Within each group, every student must be friends with every other student. Can you do it?
The trick: if two vertices are in the same clique, they MUST be connected. If two vertices are NOT connected, they MUST be in different cliques. So, build the complement graph (connect vertices that are NOT connected in the original). The two-clique problem reduces to checking if the complement graph is bipartite!
If the complement graph is bipartite, the two groups form the two cliques.
Approach 1: Brute Force (Try All Partitions)
Intuition
Try every possible way to split vertices into two groups. For each partition, check if both groups form cliques.
Algorithm
- Generate all 2^V ways to partition vertices into two groups.
- For each partition, check if both groups are cliques (all pairs within each group are connected).
- If any partition works, return true.
public class TwoCliqueBrute {
public static boolean canPartition(int V, int[][] adj) {
// Try all 2^V partitions
for (int mask = 0; mask < (1 << V); mask++) {
boolean valid = true;
// Check clique 1 (vertices in mask)
for (int i = 0; i < V && valid; i++) {
if ((mask & (1 << i)) == 0) continue;
for (int j = i + 1; j < V && valid; j++) {
if ((mask & (1 << j)) == 0) continue;
if (adj[i][j] != 1) valid = false;
}
}
// Check clique 2 (vertices not in mask)
for (int i = 0; i < V && valid; i++) {
if ((mask & (1 << i)) != 0) continue;
for (int j = i + 1; j < V && valid; j++) {
if ((mask & (1 << j)) != 0) continue;
if (adj[i][j] != 1) valid = false;
}
}
if (valid) return true;
}
return false;
}
public static void main(String[] args) {
int V = 5;
int[][] adj = {
{0,1,1,1,0},
{1,0,1,1,0},
{1,1,0,1,0},
{1,1,1,0,1},
{0,0,0,1,0}
};
System.out.println("Can partition into two cliques: " + canPartition(V, adj));
}
}Complexity Analysis
- Time Complexity: O(2^V * V²) - 2^V partitions, each checked in O(V²)
- Space Complexity: O(V²) - for the adjacency matrix
Approach 2: Optimal (Complement Graph + Bipartite Check)
Intuition
Key insight: vertices NOT connected by an edge CANNOT be in the same clique. Build the complement graph (edge where there's no edge in original, and vice versa). If the complement graph is bipartite, the two sides of the bipartition form two cliques in the original graph.
Algorithm
- Build the complement graph: add edge (u,v) if original has no edge (u,v).
- Check if the complement graph is bipartite using BFS/DFS 2-colouring.
- If bipartite → the graph can be partitioned into two cliques.
import java.util.*;
public class TwoCliqueOptimal {
public static boolean canPartition(int V, int[][] adj) {
// Build complement graph adjacency list
List<List<Integer>> complement = new ArrayList<>();
for (int i = 0; i < V; i++) complement.add(new ArrayList<>());
for (int i = 0; i < V; i++) {
for (int j = i + 1; j < V; j++) {
if (adj[i][j] == 0) { // no edge in original = edge in complement
complement.get(i).add(j);
complement.get(j).add(i);
}
}
}
// Check if complement graph is bipartite
int[] colour = new int[V];
Arrays.fill(colour, -1);
for (int i = 0; i < V; i++) {
if (colour[i] == -1) {
if (!bfs(i, complement, colour)) {
return false;
}
}
}
return true;
}
static boolean bfs(int start, List<List<Integer>> adj, int[] colour) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
colour[start] = 0;
while (!queue.isEmpty()) {
int node = queue.poll();
for (int neigh : adj.get(node)) {
if (colour[neigh] == -1) {
colour[neigh] = 1 - colour[node];
queue.offer(neigh);
} else if (colour[neigh] == colour[node]) {
return false;
}
}
}
return true;
}
public static void main(String[] args) {
int V = 5;
int[][] adj = {
{0,1,1,1,0},
{1,0,1,1,0},
{1,1,0,1,0},
{1,1,1,0,1},
{0,0,0,1,0}
};
System.out.println("Can partition into two cliques: " + canPartition(V, adj));
}
}Complexity Analysis
- Time Complexity: O(V + E) - building complement is O(V²), bipartite check is O(V + E_complement)
- Space Complexity: O(V + E) - for the complement adjacency list and colour array