<p>I am re-opening <a href="https://cstheory.stackexchange.com/questions/20843/partition-into-interval-graphs">this</a> question as i have the following question.
I was going through the <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v11i1r46/pdf" rel="nofollow noreferrer">paper by Farrugia</a> which was mentioned in an answer in that post. Initially i beleived that the follwoing problem is NP-Complete.</p>

<p>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.</p>

<p>But in the paper,there is a theorem which says </p>

<blockquote>
  <p>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.</p>
</blockquote>

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

CC BY-SA 3.0
2014-02-14T18:05:26.413Z
what is an 'additive' property ?
Suresh Venkat
CC BY-SA 3.0
2014-02-21T05:10:47.467Z
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.
JimN
<graph-theory><graph-algorithms><partition-problem><interval-graphs>
partition into unit-interval graphs
Dibyayan
# partition into unit-interval graphs

(Asked by: username_0 on 2014-02-14)

I am re-opening [this](https://cstheory.stackexchange.com/questions/20843/partition-into-interval-graphs) question as i have the following question.
I was going through the [paper by Farrugia](http://www.combinatorics.org/ojs/index.php/eljc/article/view/v11i1r46/pdf) 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 ??

**Tags:** graph-theory, graph-algorithms, partition-problem, interval-graphs

> **Comments:**
> **username_1**: what is an 'additive' property ?  
> **username_2**: 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.  

---

## 0 answers

