Rhangel's blog

Split Graph Check
By Rhangel, history, 9 years ago, In English

Hello guys!

I'm solving a problem where I need to check if a graph can be split into a click set and a set independent. I would like to know if there is any algorithm or some technique to do this type of verification.

Problem

Tks :D

  • Vote: I like it
  • +17
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
9 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

What do these two terms "click set" "set independent" mean?

→ Reply
»
9 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Let the size of the clique be X and size of the independent set be Y , Then we know that the total number of edges M must be
This is a necessary condition but then if we can somehow prove that this condition is sufficient as well then we can fix the clique size X and do subset sum dp over the degree of nodes to get number of subsets of nodes with sum of degree and size N - X.
Though i don't know how to prove that this condition is sufficient.

→ Reply
  • »
    »
    9 years ago, hide # ^ |
    ← Rev. 3  
    Vote: I like it +10 Vote: I do not like it

    We should prove that when problem's condition is not held , M-X(X-1)/2-SIGMA(d_i)!=0.

    If the condition is not held then one of these two things happened :

    • The first set is not clique : then we remove edges with one side out of the first set and we add them one by one. At first M-X(X-1)/2-SIGMA(d_i) is negative (cause M<X(X-1)/2 and SIGMA(d_i) is 0) and it won't increase by adding edges.

    • The first set in clique but the second set is not independent : then we do the same thing again. At first M=X(X-1)/2 so our value is 0. After adding edges, at least one edge's both endpoints are in the second set, and the value would decrease by one. So it can't be equal to zero at the end.

    By the way, how to do this with O(n^2) complexity?

    → Reply
  • »
    »
    9 years ago, hide # ^ |
    ← Rev. 4  
    Vote: I like it +10 Vote: I do not like it

    Yes it's sufficient: notice that sum of degrees of a subset is = number of edges which have one endpoint in that set + 2*number of edges with both endpoints in that subset = number of edges which have atleast one endpoint in that set + number of edges with both endpoints in that set. The first thing is <=m and the second thing is <= C(X,2). Equality holds iff the subset if a clique and its complement is an independent set. However subset sum dp itself is pretty slow. I have an O(n2logn) solution which gets 70/100 in the POI problem linked above: code (I am pretty sure it can be optimized to O(n2) though I didn't try it). I basically binary search for the clique size and observe a few properties. Will post details if required.

    → Reply
»
9 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

You can check if the graph is split from its degree sequence.

https://en.wikipedia.org/wiki/Split_graph#Degree_sequences

→ Reply
»
9 years ago, hide # |
← Rev. 2  
Vote: I like it +10 Vote: I do not like it

If there are no edges in the graph then (at most, see below) one of the nodes can be in the clique. Otherwise let u be the vertex with the largest degree. We have two cases:

  • If u is not in the clique then all adjacent vertices (at least one) must be in the clique and the clique size must be at least d(u) so each of the vertices must have at least d(u)-1 edges to other vertices in the clique. But since all nodes have degree at most d(u) and the adjacent nodes have an edge to u (which is not in the clique), the clique must consist exactly of the nodes adjacent to u. This means that the current graph must look like a clique of size d(u) and some isolated nodes.

  • If u is in the clique then we known that nodes not adjacent to u are not in the clique and we can remove them and u from the graph and repeat.

So the algorithm looks as follows:

  1. If there are no edges in the current graph goto 5

  2. Select the node with the largest degree and remove all nodes not adjacent to it from the graph.

  3. If the current graph is a clique (keep track of total number of nodes and edges in current graph) goto 6

  4. Remove the current node from the graph and goto 1

  5. The options for the clique are (the removed largest degree nodes) together with (at most one node from the remaining nodes).

  6. The options for the clique are (the removed largest degree nodes) together with (the remaining clique minus possibly one node).

→ Reply