论文标题
诱发的不相交路径和$ h $ free图的连接子图
Induced Disjoint Paths and Connected Subgraphs for $H$-Free Graphs
论文作者
论文摘要
路径$ p_1，\ ldots，p_k $在图中$ g =（v，e）$，如果任何两个不同的$ p_i $和$ p_j $都没有共同的顶点也不具有相邻的顶点，则会相互诱发。诱发的脱节路径问题是确定图形$ g $是否具有$ k $ k $对指定的顶点$（s_i，t_i）$包含$ k $相互诱导的路径$ p_i $，以使每个$ p_i $均从$ s_i $开始，并以$ t_i $结束。这是一个经典的图形问题，即使对于$ k = 2 $，也是NP完整的。我们引入了自然的概括，引起了连接的子图：我们必须连接终端组，而不是连接终端对。我们给出了两种问题的计算复杂性的几乎完整的二分法，即无h的图形，即不包含某些固定图H作为诱导子图的图。最后，如果固定终端集的数字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. 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$ starts from $s_i$ and ends at $t_i$. This is a classical graph problem that is NP-complete even for $k=2$. We introduce a natural generalization, Induced Disjoint Connected Subgraphs: instead of connecting pairs of terminals, we must connect sets of terminals. We give almost-complete dichotomies of the computational complexity of both problems for H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. Finally, we give a complete classification of the complexity of the second problem if the number k of terminal sets is fixed, that is, not part of the input.
