2
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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 :).

$\endgroup$
  • $\begingroup$ So I can do it with a simple DFS that colouring the different level of the graph. Thanks :) $\endgroup$ – angelst00ne Feb 21 '13 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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