Number of ways of splitting a graph

[StainlessSteel]

Hello!

My problem is:
Given a graph (for example as adjecency lists), find the number of ways to arrange it into a clique and a independent set, both non-empty.

This is to be done in O(n^2).

Any tips will be appreciated.

[Zachm]

I think there is something wrong with your requirement:
1. Given a graph, there is only one way to arrange it into a clique - connect each vertex to each other vertex - O(n^2).
2. Given a graph, there is only one way to arrange it into an indepenent set - remove all edges from the graph - O(n^2).

Regards,
Zachm

[StainlessSteel]

Thank you for your reply.

I might've stated something vaguely, but I mean arrangement such as below:

http://upload.wikimedia.org/wikipedia/commons/3/38/Split_graph.svg

The whole graph has to be divided into a clique and an independent set, both non-empty.

[Zachm]

I see what you mean, not arrangement, but dividing the vertices into 2 disjoint groups, while not touching the graph structure.

I would look at the Degree Sequence (http://en.wikipedia.org/wiki/Split_graph#Degree_sequences) of the graph, and find the maximum m which satisfies the formula in the link. This would split the graph into two parts:
A. Vertices 1 to m are part of a maximum clique.
B. Vertices m+1 to n are an independent set.

To get all other possible splits:
Let g be the number of vertices within the max-clique which are not connected to any other vertex in the independent set, then moving any of them into the independent set (and removing from the clique) will result in a new split graph. Since any of these g vertices can be either in the clique or in the independent set, there are 2^g different splits.

I hope I am not overlooking something :)

Regards,
Zachm

[StainlessSteel]

Awesome!

I really wonder how I could've missed that equation, as I've read the Split graph page some 10 times so far.


I don't agree with the combinatorics, though, as:

If g is the number of vertices in the max-clique which can be members of the indep-set as well, we're ignoring the fact that there might be vertices in the independent set which might be members of the clique. Hence I'd need to sum g (as per your description), and g' (the number of vertices in the independent set which have an edge to every member of the clique), then
N = 2^(g + g').

I'll probably code the thing tomorrow, check it against the primitive O(n^2 * 2^n) bruteforce algorithm, and see if it works.

Now, complexity:
1. Find the degree sequence - O(|V|log|V|)
2. Find our maximum m - O(|V|).
3. Test it - O(|V|).
4. Arrange our clique and indep set - O(|V|).

At this point I need to reduce the testing to constant time (otherwise the tests at quadratic complexity would turn to O(|V||E|log|E|), which is too long considering my input as adjecency list, so:

5. Build an adjecency matrix O(|V||E|).
6. Compute g and g' O(|V||E|).

Another note, an upper bound on g + g' is when the maximum indep set is ~|V|/2, and maximally interconnected with the clique. This way, g + g' is O(|V|).

As I'm facing |V| and |E| on the order of 10^3, I need bignum, but I'll just go with binary exponentation with addition on the decimal numbers.

Thanks again, I'll give you more feedback as soon as I can.

[Zachm]

I don't agree with the combinatorics, though, as:

If g is the number of vertices in the max-clique which can be members of the indep-set as well, we're ignoring the fact that there might be vertices in the independent set which might be members of the clique.

I don't think this case is possible since the clique is maximum:
Assume there is some vertex v in the IS which is connected to all vertices of the clique, it follows that degree(v) >= m and therefore it would have to be included in the clique on the first place.

Regards,
Zachm

[StainlessSteel]

Alright, my bad.

Thanks again!