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?

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ Do you know that there is a polynomial time algorithm, or are you just hoping for one? $\endgroup$
    – Luke Mathieson
    Apr 24, 2013 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, 2013 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, 2013 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, 2013 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, 2013 at 9:49

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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