8
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Do you know that there is a polynomial time algorithm, or are you just hoping for one? $\endgroup$ – Luke Mathieson Apr 24 '13 at 1:16
  • 1
    $\begingroup$ 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? $\endgroup$ – Aryabhata Apr 24 '13 at 8:14
  • $\begingroup$ @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." $\endgroup$ – Alexandre Apr 24 '13 at 9:46
  • $\begingroup$ @Alexandre: Interval graphs are special. Well known NP-Hard problems are in P, when restricted to interval graphs. $\endgroup$ – Aryabhata Apr 24 '13 at 9:48
  • $\begingroup$ @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. $\endgroup$ – Alexandre Apr 24 '13 at 9:49
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.