Induced subtrees in interval graphs
Pinar Heggernes, Pim van 't Hof and Martin Milanič
This paper appeared in the proceedings of IWOCA 2013, the 24th International Workshop on Combinatorial Algorithms (held on July 10-12, 2013 in Rouen, France), Lecture Notes in Computer Science, vol. 8288, pp. 230-243, 2013.
[DOI][Preprint]
Abstract:
The Induced Subtree Isomorphism problem takes as input a graph G and a tree T, and the task is to decide whether G has an induced subgraph that is isomorphic to T. This problem is known to be NP-complete on bipartite graphs, but it can be solved in polynomial time when G is a forest. We show that Induced Subtree Isomorphism can be solved in polynomial time when G is an interval graph. In contrast to this positive result, we show that the closely related Subtree Isomorphism problem is NP-complete even when G is restricted to the class of proper interval graphs, a well-known subclass of interval graphs.