TY - JOUR

T1 - Subgraph Isomorphism on Graph Classes that Exclude a Substructure

AU - Bodlaender, Hans L.

AU - Hanaka, Tesshu

AU - Kobayashi, Yasuaki

AU - Kobayashi, Yusuke

AU - Okamoto, Yoshio

AU - Otachi, Yota

AU - van der Zanden, Tom C.

N1 - Funding Information:
Partially supported by NETWORKS (the Networks project, funded by the Netherlands Organization for Scientific Research NWO), the ELC project (the project Exploring the Limits of Computation, funded by MEXT), JSPS/MEXT KAKENHI Grant Numbers JP24106004, JP18K11168, JP18K11169, JP18H04091, JP18H06469, JP15K00009, JST CREST Grant Number JPMJCR1402, and Kayamori Foundation of Informational Science Advancement. The authors thank Momoko Hayamizu, Kenji Kashiwabara, Hirotaka Ono, Ryuhei Uehara, and Koichi Yamazaki for helpful discussions. The authors are grateful to the anonymous reviewer of an earlier version of this paper who pointed out a gap in a proof. A preliminary version appeared in the proceedings of the 11th International Conference on Algorithms and Complexity (CIAC 2019), Lecture Notes in Computer Science 11485 (2019) 87–98.
Publisher Copyright:
© 2020, Springer Science+Business Media, LLC, part of Springer Nature.

PY - 2020/12/1

Y1 - 2020/12/1

N2 - We study Subgraph Isomorphism on graph classes defined by a fixed forbidden graph. Although there are several ways for forbidding a graph, we observe that it is reasonable to focus on the minor relation since other well-known relations lead to either trivial or equivalent problems. When the forbidden minor is connected, we present a near dichotomy of the complexity of Subgraph Isomorphism with respect to the forbidden minor, where the only unsettled case is P5, the path of five vertices. We then also consider the general case of possibly disconnected forbidden minors. We show fixed-parameter tractable cases and randomized XP-time solvable cases parameterized by the size of the forbidden minor H. We also show that by slightly generalizing the tractable cases, the problem becomes NP-complete. All unsettle cases are equivalent to P5 or the disjoint union of two P5’s. As a byproduct, we show that Subgraph Isomorphism is fixed-parameter tractable parameterized by vertex integrity. Using similar techniques, we also observe that Subgraph Isomorphism is fixed-parameter tractable parameterized by neighborhood diversity.

AB - We study Subgraph Isomorphism on graph classes defined by a fixed forbidden graph. Although there are several ways for forbidding a graph, we observe that it is reasonable to focus on the minor relation since other well-known relations lead to either trivial or equivalent problems. When the forbidden minor is connected, we present a near dichotomy of the complexity of Subgraph Isomorphism with respect to the forbidden minor, where the only unsettled case is P5, the path of five vertices. We then also consider the general case of possibly disconnected forbidden minors. We show fixed-parameter tractable cases and randomized XP-time solvable cases parameterized by the size of the forbidden minor H. We also show that by slightly generalizing the tractable cases, the problem becomes NP-complete. All unsettle cases are equivalent to P5 or the disjoint union of two P5’s. As a byproduct, we show that Subgraph Isomorphism is fixed-parameter tractable parameterized by vertex integrity. Using similar techniques, we also observe that Subgraph Isomorphism is fixed-parameter tractable parameterized by neighborhood diversity.

UR - http://www.scopus.com/inward/record.url?scp=85087442920&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85087442920&partnerID=8YFLogxK

U2 - 10.1007/s00453-020-00737-z

DO - 10.1007/s00453-020-00737-z

M3 - Article

AN - SCOPUS:85087442920

SN - 0178-4617

VL - 82

SP - 3566

EP - 3587

JO - Algorithmica

JF - Algorithmica

IS - 12

ER -