Name
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 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 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. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1007/s00453-020-00737-z | ALGORITHMICA |
Keywords | DocType | Volume |
Subgraph isomorphism, Minor-free graphs, Parameterized complexity | Journal | 82 |
Issue | ISSN | Citations |
12 | 0178-4617 | 0 |
PageRank | References | Authors |
0.34 | 0 | 7 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hans L. Bodlaender | 1 | 5699 | 375.15 |
| Tesshu Hanaka | 2 | 0 | 2.03 |
| Kobayashi Yasuaki | 3 | 0 | 0.34 |
| Yusuke Kobayashi | 4 | 106 | 21.98 |
| Yoshio Okamoto | 5 | 170 | 28.50 |
| Yota Otachi | 6 | 161 | 37.16 |
| van der Zanden Tom C. | 7 | 0 | 0.34 |