1
$\begingroup$

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.

2 Answers 2

3

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.

  • 0
    right, understood.. Thank you so much Henning! :-)2019-04-07
1

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.