论文标题
绕道图
Detours in Directed Graphs
论文作者
论文摘要
我们研究了未指向和定向图的经典最长路径问题的两个“上述保证”版本，并获得以下结果。在我们研究的最长路径的第一个变体中，任务是确定图表是否具有至少dist_g（s，t）+k（其中dist_g（s，t）的长度的（s，t）Path）表示从s到t的最短路径的长度。 Bezáková等。证明在无方向的图上，问题是固定参数可处理的（FPT），通过提供运行时间2^{o（k）} n的算法。此外，他们在打开的有向图上留下了问题的参数化复杂性。我们的第一个主要结果是在有向图上的最长绕道和有向图上的3个偶极路径之间建立了连接。使用这些新见解，我们设计了一个2^{o（k）} n^{o（1）}时间算法，用于有向平面图上的问题。此外，新方法在无向图上产生的FPT算法明显更快。 在最长路径的第二个变体中，即直径高于直径的最长路径，任务是确定该图是否具有至少长度为diam（g）+k（diam（g）（g））表示图G中最长路径的长度。我们在无方向性和有向图上获得有关最长路径的二分法结果。对于（UN）有向图，即使对于k = 1，直径上方的最长路径也是NP完整的。但是，如果输入无方向的图是2个连接的，则问题是fpt。另一方面，对于2个连接的有向图，我们表明，直径上方的最长路径可在{1，\ dots，4}中的每个k \的多项式时间内解决，并且对于每个k \ geq 5。对于通用导向的图形上图上的最长路径的参数化复杂性，对一般的开放图是一个有趣的开放问题。
We study two "above guarantee" versions of the classical Longest Path problem on undirected and directed graphs and obtain the following results. In the first variant of Longest Path that we study, called Longest Detour, the task is to decide whether a graph has an (s,t)-path of length at least dist_G(s,t)+k (where dist_G(s,t) denotes the length of a shortest path from s to t). Bezáková et al. proved that on undirected graphs the problem is fixed-parameter tractable (FPT) by providing an algorithm of running time 2^{O (k)} n. Further, they left the parameterized complexity of the problem on directed graphs open. Our first main result establishes a connection between Longest Detour on directed graphs and 3-Disjoint Paths on directed graphs. Using these new insights, we design a 2^{O(k)} n^{O(1)} time algorithm for the problem on directed planar graphs. Further, the new approach yields a significantly faster FPT algorithm on undirected graphs. In the second variant of Longest Path, namely Longest Path Above Diameter, the task is to decide whether the graph has a path of length at least diam(G)+k (diam(G) denotes the length of a longest shortest path in a graph G). We obtain dichotomy results about Longest Path Above Diameter on undirected and directed graphs. For (un)directed graphs, Longest Path Above Diameter is NP-complete even for k=1. However, if the input undirected graph is 2-connected, then the problem is FPT. On the other hand, for 2-connected directed graphs, we show that Longest Path Above Diameter is solvable in polynomial time for each k\in{1,\dots, 4} and is NP-complete for every k\geq 5. The parameterized complexity of Longest Path Above Diameter on general directed graphs remains an interesting open problem.
