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 - Zanden, Tom C. van der

PY - 2020/7/2

Y1 - 2020/7/2

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 𝑃5, 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 𝑃5 or the disjoint union of two 𝑃5’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 𝑃5, 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 𝑃5 or the disjoint union of two 𝑃5’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.

KW - Minor-free graphs

KW - Parameterized complexity

KW - Subgraph isomorphism

UR - http://www.scopus.com/inward/record.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 -