# 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? Apr 24, 2013 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? Apr 24, 2013 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." Apr 24, 2013 at 9:46
• @Alexandre: Interval graphs are special. Well known NP-Hard problems are in P, when restricted to interval graphs. Apr 24, 2013 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. Apr 24, 2013 at 9:49

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