Consider this problem:
Given an undirected graph $G = (V, E)$, find $G' = (V', E')$ such that:
- $G'$ is an induced subgraph of $G$
- $G'$ has no 3-cliques
- $|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$,
$(v_1.color == v_2.color \wedge v_2.color == v_3.color \wedge v_3.color == v_1.color) = False$
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?