# Data structure for graph, algorithm

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\cdot 10 ^6$) I need to split its vertices into as many groups as possible, but with two conditions: each pair of vertices from different groups are connected by an edge and 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. When we finish, we will have some connected components which are the answer. I think I can prove this. But, even if, it's only theoretical solution. With given constraints it's very very bad, not optimal(complemented graph can be huge with such $n$). But I believe this approach can be somehow smartly fixed. But how? I heard that this problem can be solved in $O((n+m)\log n)$ time.

Can anyone help?

For a graph with vertices indexed 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: $\left\{4\right\}, \ \left\{5,7\right\}, \ \left\{1,2,3,6\right\}$ respectively. There are edges connecting each pair of vertices from different groups and we can't create more groups.

-

Yes, it sounds right that you're looking for the connected components of the complement graph.

The problem is that the complement graph is co-sparse. But the basic strategy still works fine; you just need to move to a representation of the graph that is optimized for co-sparse graphs.

Non-neighbor lists. For each vertex in the graph, keep a sorted list of vertices that are not neighbors of the given node.

(This is easy to make if you have a conventional representation of the orginal graph: just create ordinary neighbor lists for it, then call them non-neighbor lists for the complement graph).

When you unify two nodes, instead of taking the union of their neighbor lists, take the intersection of their non-neighbor lists. This makes the non-neighbor list shorter than it was before, so the efficiency of the representation will improve as you unify nodes.

In each step of the algorithm, choose a node with as few non-neighbors as possible, and seek out a neighbor to unify it with. You can afford to seek stupidly, because almost all nodes will be neighbors. Once you find a candidate and unify the nodes, you can use the old and new non-neighbor lists to locate the non-neighbors whose own non-neighbor lists need to be adjusted as a consequence of the unification.

The algorithm stops when you discover that the node with the fewest non-neighbors is nevertheless neighbor to all of the remaining other nodes. Then no other unifications are possible, and each of the surviving nodes is the leader of a component.

You don't even need any fancy priority queue structure to keep track of which node has the fewest non-neighbors, because the lists only ever get shorter. So once you've scanned the entire graph once to find the shortest list, it will remain the shortest until you explicitly rewrite another one to become shorter. So you can keep track of that in constant space.

-
OK, I understand something after reading it twice, but I'm still concerned about time complexity. So I take the node with as few non-neighbors (in complement graph) as possible and seek out a node which is non-neighbor in given graph - to unify them. But it's just.. like creating this complement graph (which can take too much time). Even worse - I don't understand how it can work fast after some unions. Then we have situation that some nodes have very small list and to find candidate to unify I have to search all possible numbers of nodes, despite the fact that they can be unified already. –  xan Dec 30 '12 at 21:58
and to create sorted lists of non-neighbors is like $O(n^2\log n)$ I think. –  xan Dec 30 '12 at 21:59
@xan: You might want to use a tree representation of the non-neighbor sets instead. Keep a different tree containing all nodes that still exist in the graph (removing the non-leader each time you unify the two nodes), and you should be able to find a neighbor in $\log m$ time. –  Henning Makholm Dec 30 '12 at 22:10
And how on earth do you get $O(n^2\log n)$? The sum of the length of all the non-neighbor lists will be $2m$ (since each original edge is represented in exactly two of them), so it cannot take more than $O(m\log m)$ time to build them all. –  Henning Makholm Dec 30 '12 at 22:12
right, understood.. Thank you so much Henning! :-) –  xan Dec 30 '12 at 22:18

Hint: Take any vertex with the minimal degree and run the first phase of your algorithm on it before constructing the complement. Afterwards, the size of the complement can be easily bounded.

-