Subgraph Isomorphism on Graph Classes that Exclude a Substructure
Subgraph Isomorphism on Graph Classes that Exclude a Substructure
复制标题
排除子结构的图类上的子图同构
DOI：
10.1007/s00453-020-00737-z
复制
发表时间：
2020
期刊：
影响因子：
1.1
通讯作者：
van der Zanden Tom C.
中科院分区：
文献类型：
--
作者：
Bodlaender Hans L.;Hanaka Tesshu;Kobayashi Yasuaki;Kobayashi Yusuke;Okamoto Yoshio;Otachi Yota;van der Zanden Tom C.
研究了由固定禁止图定义的子图同构图类。虽然有几种方法禁止一个图，我们观察到，这是合理的，专注于次要的关系，因为其他众所周知的关系导致微不足道的或等效的问题。当禁止子图连通时，我们给出了关于禁止子图同构的复杂性的近似二分法，其中唯一未解决的情况是五个顶点的路.然后，我们还考虑可能断开禁止未成年人的一般情况。我们展示了固定参数易处理的情况下，和随机的XP时间可解的情况下，参数化的大小禁止minorH。我们还表明，通过稍微推广的听话的情况下，问题成为NP完全的。所有未解决的问题都等于或等于两个问题的不相交的结合.作为一个副产品，我们表明，SubgraphIsomorphismis固定参数易处理的顶点完整性参数化。使用类似的技术，我们还观察到，SubgraphIsomorphismis固定参数易处理参数的邻域多样性。
We study SubgraphIsomorphismon 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 SubgraphIsomorphismwith respect to the forbidden minor, where the only unsettled case is, 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 minorH. We also show that by slightly generalizing the tractable cases, the problem becomes NP-complete. All unsettle cases are equivalent toor the disjoint union of two’s. As a byproduct, we show that SubgraphIsomorphismis fixed-parameter tractable parameterized by vertex integrity. Using similar techniques, we also observe that SubgraphIsomorphismis fixed-parameter tractable parameterized by neighborhood diversity.