论文标题
几乎是不相交的路径，并通过禁止对
Almost Disjoint Paths and Separating by Forbidden Pairs
论文作者
论文摘要
根据Menger定理，在有向图中从顶点到顶点t的电弧 - 偏离路径的最大数量等于断开S和T所需的微量数量，即S-T-CUT的最小尺寸。具有单位容量的网络中的最大流量问题等效于弧线路径问题。此外，最大流量和最低切割问题形成了强烈双重对。我们放宽了路径上的脱节要求，使它们几乎是脱节的，这意味着它们可能会共享一个弧线。由此产生的几乎不相交的路径问题（ADP）要求k s-t paths，以使其中的任何两个几乎都是脱节的。禁止对问题（SFP）是相应的双重问题，并需要一组K弧对，使每个S-T-Path都包含两个至少一对的弧。 在本文中，我们探讨了这两个问题，表明它们通常具有无限的二元性差距并分析其复杂性。我们证明，当k是输入的一部分时，ADP是NP兼容，即使对于无环图，SFP也是SIGMA_2P complete。此外，当固定k <= 2时，我们有效地解决了ADP，并在k恒定且所考虑的图为acyclic时基于ADP的动态编程提供多项式时间算法。
By Menger's theorem the maximum number of arc-disjoint paths from a vertex s to a vertex t in a directed graph equals the minumum number of arcs needed to disconnect s and t, i.e., the minimum size of an s-t-cut. The max-flow problem in a network with unit capacities is equivalent to the arc-disjoint paths problem. Moreover the max-flow and min-cut problems form a strongly dual pair. We relax the disjointedness requirement on the paths, allowing them to be almost disjoint, meaning they may share up to one arc. The resulting almost disjoint paths problem (ADP) asks for k s-t-paths such that any two of them are almost disjoint. The separating by forbidden pairs problem (SFP) is the corresponding dual problem and calls for a set of k arc pairs such that every s-t-path contains both arcs of at least one such pair. In this paper, we explore these two problems, showing that they have an unbounded duality gap in general and analyzing their complexity. We prove that ADP is NP-complete when k is part of the input and that SFP is Sigma_2P-complete, even for acyclic graphs. Furthermore, we efficiently solve ADP when k<=2 is fixed and present a polynomial time algorithm based on dynamic programming for ADP when k is constant and the considered graphs are acyclic.
