Subgraph Isomorphism on Graph Classes that Exclude a Substructure

Hans L. Bodlaender; Tesshu Hanaka; Yasuaki Kobayashi; Yusuke Kobayashi; Yoshio Okamoto; Yota Otachi; Tom C. van der Zanden

doi:10.1007/s00453-020-00737-z

Subgraph Isomorphism on Graph Classes that Exclude a Substructure

Hans L. Bodlaender, Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, Tom C. van der Zanden

Research output: Contribution to journal › Article › Academic › peer-review

Abstract

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.

Original language	English
Pages (from-to)	3566-3587
Number of pages	22
Journal	Algorithmica
Volume	82
Issue number	12
Early online date	2020
DOIs	https://doi.org/10.1007/s00453-020-00737-z
Publication status	Published - 2 Jul 2020

Funding

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.

Keywords

Minor-free graphs
Parameterized complexity
Subgraph isomorphism

Access to Document

10.1007/s00453-020-00737-z

Bodlaender2020_Article_SubgraphIsomorphismOnGraphClasFinal published version, 3.04 MBLicence: Taverne

Cite this

@article{c03349ec337348329c68ca3717e6a1b9,

title = "Subgraph Isomorphism on Graph Classes that Exclude a Substructure",

abstract = "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{\textquoteright}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.",

keywords = "Minor-free graphs, Parameterized complexity, Subgraph isomorphism",

author = "Bodlaender, {Hans L.} and Tesshu Hanaka and Yasuaki Kobayashi and Yusuke Kobayashi and Yoshio Okamoto and Yota Otachi and Zanden, {Tom C. van der}",

year = "2020",

month = jul,

day = "2",

doi = "10.1007/s00453-020-00737-z",

language = "English",

volume = "82",

pages = "3566--3587",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York",

number = "12",

}

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 -

Subgraph Isomorphism on Graph Classes that Exclude a Substructure

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this