This question already has an answer here:

I am re-opening this question as i have the following question. I was going through the paper by Farrugia which was mentioned in an answer in that post. Initially i beleived that the follwoing problem is NP-Complete.

Suppose there is a graph $G=(V,E)$. I want to test if V can be partitioned into two disjoint sets $V_1$ and $V_2$ such that the subgraphs induced by $V_1$ and $V_2$ are unit interval graphs.

But in the paper,there is a theorem which says

Let $A$ and $B$ be additive induced-hereditary properties. Then there is a polynomial-time transformation from the $A$-recognition problem to the $(A◦B)$-recognition problem.

So, my question is that :- is it possible that because of the above theorem the problem might be solvable in polynomial time ??


marked as duplicate by Jeffε, David Eppstein, Kaveh, Sasho Nikolov, Radu GRIGore Nov 5 '14 at 8:18

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ what is an 'additive' property ? $\endgroup$ – Suresh Venkat Feb 14 '14 at 18:05
  • 2
    $\begingroup$ That paper's main theorem shows that your problem is NP hard, as I think unit interval graphs satisfy the conditions of the hardness proof. The theorem you cite does not help in recognizing (A◦B) graphs... many easy problems can polynomially reduce to a hard problem. E.g. Every problem in P polynomially reduces to an NP-complete problem. $\endgroup$ – JimN Feb 21 '14 at 5:10