Subgraph Isomorphism on Graph Classes that Exclude a Substructure
- PDF / 1,806,727 Bytes
- 22 Pages / 439.37 x 666.142 pts Page_size
- 74 Downloads / 206 Views
Subgraph Isomorphism on Graph Classes that Exclude a Substructure Hans L. Bodlaender1 · Tesshu Hanaka2 · Yasuaki Kobayashi3 · Yusuke Kobayashi3 · Yoshio Okamoto4,5 · Yota Otachi6 · Tom C. van der Zanden7 Received: 28 June 2019 / Accepted: 13 June 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
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 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. Keywords Subgraph isomorphism · Minor-free graphs · Parameterized complexity
1 Introduction Let Q and G be graphs. A subgraph isomorphism 𝜂 is an injection from V(Q) to V(G) that preserves the adjacency in Q; that is, if {u, v} ∈ E(Q) , then {𝜂(u), 𝜂(v)} ∈ E(G) . We say that Q is subgraph-isomorphic to G if there is a subgraph isomorphism from Q to G, and write Q ⪯ G . In this paper, we study the following problem of deciding the existence of a subgraph isomorphism.
* Yota Otachi otachi@nagoya‑u.jp Extended author information available on the last page of the article
13
Vol.:(0123456789)
Algorithmica
The problem Subgraph Isomorphism is one of the most general and fundamental graph problems and generalizes many other graph problems such as Graph Isomorphism, Clique, Hamiltonian Path/Cycle, and Bandwidth. Obviously, Subgraph Isomorphism is NP-complete in general. When both host and pattern graphs are restricted to be in a graph class C , we call the problem Subgraph Isomorphism on C . By slightly modifying known reductions in [7, 15], one can easily show that the problem is hard even for very restricted graph classes such as linear forests and cluster graphs. (See Proposition 1.1.) Since most of the well-studied graph classes contain all linear forests or all cluster graphs, it is often hopeless to have a polynomial-time algorithm for an interesting graph class. This is sometimes true even if we further assume that the graphs are connected [20, 22]. On the other hand, it is polynomial-time solvable for trees [29]. This result was first generalized for 2-connected outerplanar
Data Loading...
