Using disjoint-set data structure, graph theory

Question

I'm practicing solving programming problems in free time. This problem I spotted some time ago and still don't know how to solve it:

For a given undirected graph with n vertices and m edges (both less than 2 × 10⁶) I need to split its vertices into as many groups as possible, but with one condition: each pair of vertices from different groups are connected by edge. Each vertex is in exactly one group. At the end I need to know the size of each group.

I was proud when I came up with this solution: consider complemented graph of the original graph and use Disjoint-set data structure for it. It gives us the right answer (not difficult to prove). But it's only theoretical solution. With given constraints it's very very bad, not optimal. But I believe this approach can be somehow smartly fixed. But how?

Can anyone help?

EDIT: for a graph with vertices from 1 to 7 and 16 edges:

1 3

1 4

1 5

2 3

3 4

4 5

4 7

4 6

5 6

6 7

2 4

2 7

2 5

3 5

3 7

1 7

we have 3 groups with sizes: 1, 2 and 4.

These groups are: {4}, {5,7}, {1,2,3,6} respectively. There are edges connecting each pair of vertices from different groups and we can't create more groups.

when you say each pair of vertices from different groups are connected by edge, do you mean they're connected by, at most, one edge? and, if not, from each pair of vertices from different groups must have an edge, do you mean if you have groups A{a, b}, B{c, d} then there must be edges from a to c and d, and from b to c and d? — Rubens
each pair of vertices from different groups are connected by an edge. If we have groups A{a,b} and B{c,d} as you said, then they are groups iff there exist edges a-c, a-d, b-c,b-d; we have to create as many groups as possible, so if there don't exist edges a-b or c-d then we can split A or B into two groups. — xan
in the last sentence, you mean if there don't exist edges a-c or a-d, right? or do the vertices in the same group must have edges in between them? — Rubens
I'm sorry, I made a mistake. I edited my question and gave an example which will clarify everything. — xan
Are you sure about the result you posted? Or did I misunderstand the problem? — Rubens

tmyklebu tmyklebu · Accepted Answer · 2012-12-29T18:56:45

I think the only ingredient you're missing is how to deal with sparse graphs.

Let's think about this in terms of finding the biggest possible complete graph where the only operation I can do is group a set of nodes (say v_1, ..., v_k) together and give the new supernode edges only to those nodes u that were connected to all of v_1, ..., v_k.

If your graph has fewer than n^2/4 edges, randomly sample n node pairs, noting which pairs are not joined by an edge. Union-find is an easy way to code this up. Now rebuild the graph using as groups the sets you found by this random sampling. Recurse on this reduced graph. (I'm not quite sure how to analyse this step, but I believe each sample-rebuild cycle reduces the graph size by at least a constant factor with high probability, so this whole process takes near-linear time.)

Once you have a fairly dense graph (at least n^2/4 edges), you can convert to an adjacency matrix representation and do exactly what you were suggesting --- check all node pairs, do a union whenever you see that two nodes aren't joined by an edge, and read off the sets.

Using disjoint-set data structure, graph theory

1 Answers