Finding the largest 3-clique-free induced subgraph

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?

• Do you know that there is a polynomial time algorithm, or are you just hoping for one? – Luke Mathieson Apr 24 '13 at 1:16
• I just realized, your two definitions of the problem don't match! The second imposes the condition that subgraph induced by $V-V'$ is also triangle free. I know that it is NP-Complete to even determine if such a partition exists: cstheory.stackexchange.com/questions/65/h-free-cut-problem. While the initial description allows the induced graph of $V-V'$ to contain triangles. Which one is the correct one? – Aryabhata Apr 24 '13 at 8:14
• @LukeMathieson: I believe a class o graphs have polynomial-time solutions because I reached the problem above from the following problem which has polynomial-time solution: "Given a set of N integer intervals, pick as many as possible so that no 3 intersect." – Alexandre Apr 24 '13 at 9:46
• @Alexandre: Interval graphs are special. Well known NP-Hard problems are in P, when restricted to interval graphs. – Aryabhata Apr 24 '13 at 9:48
• @Aryabhata: The induced subgraph is G', and it cannot have any 3-cliques. Therefore, it cannot have any triangles, exactly the same as the second description. – Alexandre Apr 24 '13 at 9:49

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