Ganian Robert, Ordyniak Sebastian
Algorithms and Complexity Group, Vienna University of Technology, Vienna, Austria.
Algorithms Group, University of Sheffield, Sheffield, UK.
Algorithmica. 2021;83(2):726-752. doi: 10.1007/s00453-020-00772-w. Epub 2020 Oct 21.
This paper revisits the classical edge-disjoint paths (EDP) problem, where one is given an undirected graph and a set of terminal pairs and asks whether contains a set of pairwise edge-disjoint paths connecting every terminal pair in . Our aim is to identify structural properties (parameters) of graphs which allow the efficient solution of EDP without restricting the placement of terminals in in any way. In this setting, EDP is known to remain NP-hard even on extremely restricted graph classes, such as graphs with a vertex cover of size 3. We present three results which use edge-separator based parameters to chart new islands of tractability in the complexity landscape of EDP. Our first and main result utilizes the fairly recent structural parameter tree-cut width (a parameter with fundamental ties to graph immersions and graph cuts): we obtain a polynomial-time algorithm for EDP on every graph class of bounded tree-cut width. Our second result shows that EDP parameterized by tree-cut width is unlikely to be fixed-parameter tractable. Our final, third result is a polynomial kernel for EDP parameterized by the size of a minimum feedback edge set in the graph.
本文重新审视经典的边不相交路径（EDP）问题，在该问题中，给定一个无向图和一组终端对，询问图中是否包含一组成对边不相交的路径，这些路径连接了中的每一对终端。我们的目标是确定图的结构属性（参数），这些属性允许高效解决EDP，而不以任何方式限制终端在图中的放置。在这种情况下，已知即使在极其受限的图类上，如具有大小为3的顶点覆盖的图，EDP仍然是NP难的。我们给出了三个结果，这些结果使用基于边分离器的参数在EDP的复杂度景观中描绘新的可处理区域。我们的第一个也是主要的结果利用了相当新的结构参数树割宽（一个与图浸入和图割有基本联系的参数）：我们为每个有界树割宽的图类上的EDP获得了一个多项式时间算法。我们的第二个结果表明，以树割宽为参数的EDP不太可能是固定参数可处理的。我们最后的第三个结果是一个多项式核，用于以图中最小反馈边集的大小为参数的EDP。
