Induced subgraph isomorphism on proper interval and bipartite permutation graphs
Pinar Heggernes, Pim van 't Hof, Daniel Meister and Yngve Villanger
Theoretical Computer Science, vol. 562, pp. 252-269, 2015.
[DOI][Preprint]
Some results of this paper appeared previously in a paper entitled "Induced subgraph isomorphism on interval and proper interval graphs", which appeared in the proceedings of ISAAC 2010, the 21st International Symposium on Algorithms and Computation (held on December 15-17, 2010, Jeju Island, Korea), Lecture Notes in Computer Science, vol. 6507, pp. 399-409, 2010.
[DOI]
Abstract:
Given two graphs G and H as input, the Induced Subgraph Isomorphism (ISI) problem is to decide whether G has an induced subgraph that is isomorphic to H. This problem is NP-complete already when G and H are restricted to disjoint unions of paths, and consequently also NP-complete on proper interval graphs and on bipartite permutation graphs. We show that ISI can be solved in polynomial time on proper interval graphs and on bipartite permutation graphs, provided that H is connected. As a consequence, we obtain that ISI is fixed-parameter tractable on these two graph classes, when parametrised by the number of connected components of~H. Our results contrast and complement the following known results: W[1]-hardness of ISI on interval graphs when parametrised by the number of vertices of H, NP-completeness of ISI on connected interval graphs and on connected permutation graphs, and NP-completeness of Subgraph Isomorphism on connected proper interval graphs and connected bipartite permutation graphs.