Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I need to find a solution to the following question: The problem of the "Two Clique" is in P or NP-complete (assuming P != NP)?

The "Two Clique" problem is the following: Given a graph G = (V, E), can V be partitioned into two non-empty parts V1, V2 such that V = V1 ∪ V2 and both V1 and V2 are cliques in G?

I was thinking about an approach based on an algorithm for bipartite graphs, what do you think about it?

share|improve this question

1 Answer 1

up vote 5 down vote accepted

By taking the complement graph, i.e., replacing $E$ with $E'$ where $e \in E'$ iff $e \not\in E$, we get the related problem: Let $G = (V,E)$ be a graph. Can $V$ be partitioned into two non-empty parts such that $V1$ and $V2$ are independent sets?

This problem is then actually equivalent to asking whether $(V,E)$ is a bipartite graph. An approach to solve this could be the following:

  1. Color all vertices gray.
  2. Choose some initial vertex $v_0$ and color it white.
  3. If there are no more gray vertices, the graph is bi-partitie, as witnessed by its coloring.
  4. If some white vertex has a white neighbour, the graph is not bipartite.
  5. Color all gray vertices with a white neighbour black.
  6. If some black vertex has a black neighbour, the graph is not bipartite.
  7. Color all gray vertices with a black neighbour white.
  8. Go to step 4.

Changing this to an algorithm for 2-Clique is straightforward, and it is easy to show that this algorithm runs in polynomial time.

Edit: The algorithm as stated deals only with the case where $(V,E)$ is connected. For non-connected graphs, add a step 7.5: If, in the last round of the algorithm, no vertex got a new color (i.e., in line 5 and 7, no change occured), choose any gray vertex and color it black or white.

A good choice of coloring strategy for the original problem is easy to find and left as an exercise to the reader :).

share|improve this answer
    
So I can do it with a simple DFS that colouring the different level of the graph. Thanks :) –  angelst00ne Feb 21 '13 at 13:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.