Subgraph Isomorphism on Graph Classes that Exclude a Substructure

• Published in: Algorithmica 2020-12, Vol.82 (12), p.3566-3587
• Main Authors: Bodlaender, Hans L., Hanaka, Tesshu, Kobayashi, Yasuaki, Kobayashi, Yusuke, Okamoto, Yoshio, Otachi, Yota, van der Zanden, Tom C.
• Format: Article
• Language: English
• Subjects: Algorithm Analysis and Problem Complexity; Algorithms; Apexes; Computer Science; Computer Systems Organization and Communication Networks; Data Structures and Information Theory; Equivalence; Isomorphism; Mathematics of Computing; Parameterization; Parameters; Substructures; Theory of Computation
• ISSN: 0178-4617; 1432-0541
• DOI: 10.1007/s00453-020-00737-z

We study S ubgraph I somorphism 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 S ubgraph I somorphism with respect to the forbidden minor, where the only unsettled case is P 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 P 5 or the disjoint union of two P 5 ’s. As a byproduct, we show that S ubgraph I somorphism is fixed-parameter tractable parameterized by vertex integrity. Using similar techniques, we also observe that S ubgraph I somorphism is fixed-parameter tractable parameterized by neighborhood diversity.