论文标题
在无截图图中引起的偏离路径
Induced Disjoint Paths in AT-free Graphs
论文作者
论文摘要
路径$ p_1，\ ldots，p_k $ in Graph $ g =（v，e）$如果任何两个不同的$ p_i $和$ p_j $既没有共同的顶点也不具有相邻的顶点（除了它们的终极偏见）。诱发的不相交路径问题是确定图形$ g $是否带有$ k $对指定的顶点$（s_i，t_i）$包含$ k $相互诱导的路径$ p_i $，以便每个$ p_i $连接$ s_i $ s_i $ and $ t_i $。这是一个经典的图形问题，即使对于$ k = 2 $，也是NP完整的。我们研究它以获取无局部图。 与其置换图和可可占性图的子类别不同，无原形图的类别没有几何相交模型。但是，通过对无及无图形图的诱发不相交路径行为的新结构分析，我们证明即使$ k $是输入的一部分，也可以在多项式时间内以多项式求解。这与其他众所周知的图形类别（例如平面图，无爪图）或更近的情况（Theta，Wheel） - 无用图相反，该结果只有在固定$ K $时才能保留。 由于我们的主要结果，决定给定的无图形是否包含固定图$ H $，作为诱导拓扑辅助的问题是多项式时间算法。此外，我们表明，通过证明问题是W [1] - hard，即使是在无用图的子类，即cobipartite图形上，这种算法实质上是最佳的。我们还表明，即使$ k $是输入的一部分，这些问题$ k $ -in-in-a-path和$ k $ -in-in-a-tree是多项式时间的可求解。这些问题是测试图形是否分别具有诱导路径或诱导树，分别跨越了$ k $给定的顶点。
Paths $P_1,\ldots,P_k$ in a graph $G=(V,E)$ are mutually induced if any two distinct $P_i$ and $P_j$ have neither common vertices nor adjacent vertices (except perhaps their end-vertices). The Induced Disjoint Paths problem is to decide if a graph $G$ with $k$ pairs of specified vertices $(s_i,t_i)$ contains $k$ mutually induced paths $P_i$ such that each $P_i$ connects $s_i$ and $t_i$. This is a classical graph problem that is NP-complete even for $k=2$. We study it for AT-free graphs. Unlike its subclasses of permutation graphs and cocomparability graphs, the class of AT-free graphs has no geometric intersection model. However, by a new, structural analysis of the behaviour of Induced Disjoint Paths for AT-free graphs, we prove that it can be solved in polynomial time for AT-free graphs even when $k$ is part of the input. This is in contrast to the situation for other well-known graph classes, such as planar graphs, claw-free graphs, or more recently, (theta,wheel)-free graphs, for which such a result only holds if $k$ is fixed. As a consequence of our main result, the problem of deciding if a given AT-free graph contains a fixed graph $H$ as an induced topological minor admits a polynomial-time algorithm. In addition, we show that such an algorithm is essentially optimal by proving that the problem is W[1]-hard with parameter $|V_H|$, even on a subclass of AT-free graph, namely cobipartite graphs. We also show that the problems $k$-in-a-Path and $k$-in-a-Tree are polynomial-time solvable on AT-free graphs even if $k$ is part of the input. These problems are to test if a graph has an induced path or induced tree, respectively, spanning $k$ given vertices.
