The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
复制标题
欧拉图和四边连通图中的边不相交路径问题
DOI：
10.1007/s00493-014-2828-6
复制
发表时间：
2015
期刊：
影响因子：
1.1
通讯作者：
Ken-ichi Kawarabayashi and Yusuke Kobayashi
中科院分区：
文献类型：
--
作者：
監修：浅野美智恵;分担著者名:只浦寛子;Ken-ichi Kawarabayashi and Yusuke Kobayashi
在边不交路径问题中，我们被给出了一个图和一组k对顶点，我们必须确定该图是否有连接给定终端对的不交路径。Robertson和Seymour的图小投影给出了这个问题的一个多项式时间算法，但他们的正确性证明需要整个图小投影。我们给出了边不相交路径问题的一个更快的算法和一个更简单的正确性证明。我们的结果可以总结如下：1.如果一个输入图是4边连通的或欧拉的，那么我们的算法只需要寻找以下三个简单的约简：(I)排除高次顶点。(Ii)不包括≤3-Edge-Cut。2.当输入图是4边连通的或欧拉图时，允许终端数为非平凡的超常数，对任意−ε；0，最高tok=O((ε)1/2)。此外，如果输入图是4边连通平面或欧拉平面，则对任意−ε>；0.3，允许Ko((lognçε))。我们还给出了一般图中边不相交路径问题的算法。我们基本上遵循罗伯逊-西摩的算法，但我们削减了他们算法正确性证明的一半。此外，我们的算法比Robertson和Seymour的算法更快。
In the edge-disjoint paths problem, we are given a graph and a set ofkpairs of vertices, and we have to decide whether or not the graph haskedge-disjoint paths connecting given pairs of terminals. Robertson and Seymour’s graph minor project gives rise to a polynomial time algorithm for this problem for any fixedk, but their proof of the correctness needs the whole Graph Minor project. We give a faster algorithm and a much simpler proof of the correctness for the edge-disjoint paths problem. Our results can be summarized as follows:1.If an input graph is either 4-edge-connected or Eulerian, then our algorithm only needs to look for the following three simple reductions: (i) Excluding vertices of high degree. (ii) Excluding ≤3-edge-cuts. (iii) Excluding large clique minors.2.When an input graph is either 4-edge-connected or Eulerian, the number of terminalskis allowed to be a non-trivially super constant number, up tok=O((log log logn)½−ε) for anyε> 0. In addition, if an input graph is either 4-edge-connected planar or Eulerian planar,kis allowed to beO((logn½−ε) for anyε> 0.3.We also give our own algorithm for the edge-disjoint paths problem in general graphs. We basically follow the Robertson-Seymour’s algorithm, but we cut half of the proof of the correctness for their algorithm. In addition, our algorithm is faster than Robertson and Seymour’s.