Two Clique Problem

The problem, simply

You get a graph: kids are dots and friendships are lines. A clique is a group where every two members are friends. Can you split all the kids into two groups so that each group is a clique? A group may be empty.

Give back true or false.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every way to split the kids into two teams, and check both.

1. For every number mask from 0 to 2^V - 1, put kid i on team A if bit i is on, otherwise on team B.
2. Check that every two kids on team A are friends, and the same for team B.
3. If some split passes, answer true.

class TwoCliqueBrute {
    public static boolean canSplit(boolean[][] friends) {
        int n = friends.length;
        for (int mask = 0; mask < (1 << n); mask++) {  // bit i on: kid i is on team A
            if (isTeam(friends, mask, true) && isTeam(friends, mask, false)) return true;
        }
        return false;
    }

    // every two kids on the chosen side must be friends
    static boolean isTeam(boolean[][] friends, int mask, boolean side) {
        int n = friends.length;
        for (int i = 0; i < n; i++) {
            if (((mask >> i & 1) == 1) != side) continue;
            for (int j = i + 1; j < n; j++) {
                if (((mask >> j & 1) == 1) != side) continue;
                if (!friends[i][j]) return false;
            }
        }
        return true;
    }
}

How long it takes: 2^V splits, each checked in O(V^2), so O(2^V * V^2). Extra room: O(V) for the loop and call. Thirty kids already means a billion splits.

Way 2: the clever way

Draw the stranger lines instead. That picture is the complement graph: it has a line exactly where the friendship graph does not. Two kids joined by a stranger line must be on different teams. So the question becomes: can the complement graph be painted with two colors so that every line joins different colors? That is the test for a bipartite graph.

1. Give every kid "no team yet".
2. Pick a kid without a team, put them on team A, and put them in a waiting line (a queue).
3. Take a kid u from the front. For every other kid v who is not friends with u: if v has no team, give v the other team and add v to the line. If v already has the same team as u, answer false.
4. Repeat from step 2 until every kid has a team. Then answer true.

When it fails, the stranger graph has a loop with an odd number of kids. In the line of friends 0-1-2-3-4, the strangers 0, 2 and 4 form a triangle of stranger lines, and a triangle cannot be painted with two colors.

class TwoCliqueSmart {
    public static boolean canSplit(boolean[][] friends) {
        int n = friends.length;
        int[] team = new int[n];
        Arrays.fill(team, -1);                         // -1: no team yet
        Queue<Integer> line = new ArrayDeque<>();
        for (int s = 0; s < n; s++) {
            if (team[s] != -1) continue;
            team[s] = 0;
            line.add(s);
            while (!line.isEmpty()) {
                int u = line.poll();
                for (int v = 0; v < n; v++) {
                    if (v == u || friends[u][v]) continue;   // only follow stranger lines
                    if (team[v] == -1) {
                        team[v] = 1 - team[u];         // strangers go on the other team
                        line.add(v);
                    } else if (team[v] == team[u]) {
                        return false;                  // two strangers forced onto one team
                    }
                }
            }
        }
        return true;
    }
}

How long it takes: every kid leaves the line once and looks at all other kids, O(V^2). We never build the stranger graph; we read it from the friendship table on the fly. Extra room: the teams and the line, O(V).

Watch out for

• Kids with no stranger lines (friends with everybody) can go on either team. The outer loop gives them a team anyway.
• The stranger graph may come in several pieces. Start a new painting from every kid without a team, not only from kid 0.
• Do not count a kid as a stranger to themselves. Skip v == u.
• An empty team is allowed, so a class where everyone is friends is true.

What interviewers ask next

• Split into three cliques? Now the stranger graph must be painted with three colors, and 3-coloring is NP-hard. There is no known fast method.
• Split into two groups where nobody in a group is friends (two independent sets)? That is the bipartite test on the friendship graph itself.
• Return the teams, not just yes or no. The team array already holds them.
• Make the two teams as equal in size as possible. Each piece of the stranger graph can be flipped as a whole, so it becomes a small subset sum over the pieces.

Remember this

Grown-up words: the kids are vertices, friendships are edges, an all-friends team is a clique, the stranger graph is the complement graph, and painting with two colors so every line joins different colors is a bipartite check with BFS.