[Solved]: Finding the largest 3-clique-free induced subgraph

ignougroup
Problem Detail: Consider this problem:

Given an undirected graph $G = (V, E)$, find $G’ = (V’, E’)$ such that:

  1. $G’$ is an induced subgraph of $G$
  2. $G’$ has no 3-cliques
  3. $|V’|$ is maximal

So the least number of vertices must be eliminated from $G$ so that 3-cliques are eliminated. An equivalent problem would be to find a 2-coloring for $G$ such that if $(v_1, v_2, v_3) in V$ and $((v_1, v_2), (v_2, v_3), (v_3, v_1)) in V$,

  1. $(v_1.color == v_2.color wedge v_2.color == v_3.color wedge v_3.color == v_1.color) = False$
  2. The (absolute) difference between the number of nodes with color 1 and the number of nodes with color 2 is maximal.

Can anyone think of a polynomial-time algorithm to solve one of these problems?

Asked By : Alexandre

Answered By : Aryabhata

Both definitions leave your problem NP-hard, and have been answered on cstheory.

  • Interpretation 1, where you require the largest triangle free sub-graph, is NP-Hard and has been answered here.
  • Intepretation 2, where you need a partition such that both the induced sub-graphs are triangle free, has been answered here.

Note that the answers I linked to are for general $H$-freeness and are a class of $NP$-Hard problems.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11518