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

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