论文标题
$ h $ free Graphs几乎没有引起的脱节路径
Few Induced Disjoint Paths for $H$-Free Graphs
论文作者
论文摘要
路径$ p^1，\ ldots，图$ g =（v，e）$中的p^k $，如果任何两个不同的$ p^i $和$ p^j $既没有共同的顶点也不具有相邻的顶点。对于固定的整数$ k $，$ k $诱导的脱节路径问题是确定图形$ g $带有$ k $ pairs的指定顶点$（s_i，t_i）$包含$ k $ k $ kumaintaly诱导的路径$ p^i $，以便每个$ p^i $从$ s_i $开始，并且以$ s_i $启动$ t_i $。虽然非诱导的版本众所周知是每个固定整数$ k $的多项式时间溶液，但文献的经典结果表明，即使是$ 2 $诱导的脱节路径也是NP的完整途径。如果输入仅限于$ h $ free Graphs，即没有固定的图形$ H $作为诱导子图，我们证明了$ k $诱导的不相交路径的新复杂性结果。我们将结果与诱发不相交路径的复杂性二分法进行了比较，这是$ 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. For a fixed integer $k$, the $k$-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$ starts from $s_i$ and ends at $t_i$. Whereas the non-induced version is well-known to be polynomial-time solvable for every fixed integer $k$, a classical result from the literature states that even $2$-Induced Disjoint Paths is NP-complete. We prove new complexity results for $k$-Induced Disjoint Paths if the input is restricted to $H$-free graphs, that is, graphs without a fixed graph $H$ as an induced subgraph. We compare our results with a complexity dichotomy for Induced Disjoint Paths, the variant where $k$ is part of the input.
