最长路径问题

在图论和理论计算机科学中，最长路径问题是指在给定的图中找出长度最长的简单路径。一条不具有任何重复顶点的路径被称为简单路径。无权图中路径的长度就是边的数量，而有权图中路径长度是边权重之和。不同的是，与此相反的最短路径问题（不含负权环）可以在多项式时间内解决。而最长路径问题是NP困难的，这意味着除非P = NP，否则对应于任意的图，没有办法在多项式时间内解决该问题。更强的结果表明这个问题也难以近似地得出答案。但是，有一个线性时间的方法可以用于有向无环图，这对于发现调度问题中的关键路径有重要的作用。

NP-困难性

可以从哈密顿路径问题规约到未加权最长路径问题，这显示出后者属于NP-困难类别：当且仅当图G的最长路径的长度是n−1时（n是图中顶点的数量），图G有哈密顿路径。由于哈密顿路径问题是NP完全的，此规约表明最长路径问题的决定版本也是NP完全的。在该决定问题中，输入是图G和数k；如果G中存在至少一条由k条或更多条边的路径，则输出为“是”，否则为“否”。^[1]

如果可以在多项式时间内解决最长路径问题，则可以通过找到最长路径，然后将其长度与数k进行比较来将其用于解决该决定问题。因此，最长的路径问题是NP难的。问题“在给定图中是否存在具有至少k条边的简单路径”是NP完全的。^[2]

在具有非负边权的加权完全图中，加权最长路径问题与旅行推销员问题相同，因为最长路径总是包括所有顶点。^[3]

无环图

在加权图G中两个给定顶点s和t之间的最长路径，与通过将G中每个权重改变为其相反数所导出的图-G中的最短路径相同。因此，如果在-G中找到最短路径，则在G中也可以找到最长路径。^[4]

对于大多数图而言，此变换并无用途，因为它在-G中产生了负环。但是如果G是有向无环图（DAG），则不会有负环，并且通过对-G中的最短路径应用线性时间算法，可以在线性时间里找到G的最长路径，因-G也是有向无环图。^[5]

对于给定DAG中的每个顶点v，可以通过以下步骤获得以v结尾的最长路径的长度：

找到给定DAG的拓扑排序。
对于DAG的每个顶点v，在拓扑排序中，通过检查连入的邻接点，并将这一个邻接点记录的最大长度加1来计算以v结尾的最长路径的长度。如果v没有连入的邻接点，则将以v结尾的最长路径的长度设置为零。在所有情况下，记录下这个数，以便算法的后续步骤访问它。

完成此操作后，可以从记录值最大的顶点v开始，然后向后找记录值最大的连入邻接点，最后反转这条路径就是结果。这和在-G上运行最短路算法等价。

关键路径

关键路径方法是进行工程项目计划时常用的一种估算项目所需时间的方法。使用时，需要构造有向无环图，其中顶点表示项目里程碑，边表示达到某一个里程碑之后，要通向另一个里程碑所必须的活动；通过估计完成相应活动将花费的时间，算出每条边的边权。在这样的图中，从第一个里程碑到最后一个里程碑的最长路径是关键路径，它描述了完成项目的总时间。^[5]

有向无环图的最长路径也可以用于分层图绘制（英语：layered graph drawing）：将有向无环图G的每个顶点v分到层数是以v结尾的最长路径长度的层，这种层分配使G的层数最小。^[6]

图的特例

迪杰斯特拉在20世纪60年代提出了一种用于在树中找到最长路径的线性时间算法，而该算法的正式证明于2002年出版。^[7]此外，最长路径可以在加权树上，块图（英语：Block graph）上，仙人掌图（英语：Cactus graph）上，^[8]二分置换图（英语：Permutation graph）上，^[9]和托勒密图（英语：Ptolemaic graph）上^[10]以多项式时间计算。

对于区间图（英语：Interval graph），已知 $O(n^{4})$ 时间的算法，其使用动态规划方法。^[11]这种动态规划方法已被用于获得Circular-arc 图（英语：Circular-arc graph）^[12]和可比性补图（即可比性图（英语：Comparability graph）的补图，也包含置换图（英语：Permutation graph））^[13]的多项式时间算法，两者具有相同的运行时间 $O(n^{4})$ 。后一种算法基于可比性补图的词典深度优先搜索（LDFS）顶点排序的特殊属性。^[14]对于共同可比性图，还已知有较高运行时间 $O(n^{7})$ 的另一种多项式时间算法，其基于由输入的可比性补图的补图定义的偏序关系的哈斯图。^[15]

此外，最长路径问题可以在树宽有界或团宽有界的任何图上在多项式时间内解决，例如距离-遗传图（英语：Distance-hereditary graph）。最后，在哈密顿路径问题是NP难的所有图上显然最长路径问题也是NP难的，例如在分割图（英语：Split graph），圆图（英语：Circle graph）和平面图上。

参数化复杂性

当通过路径长度参数化时，最长路径问题是固定参数易处理的。例如，可以通过执行以下步骤的算法，以输入图大小的线性时间求解最长路径问题（但对于路径长度呈指数时间）：

对图进行深度优先搜索。设 $d$ 是得到的深度优先搜索树（英语：Trémaux tree）的深度。
使用深度优先搜索树的根到叶路径的顺序，按照搜索遍历的顺序，构建图的路径分解（英语：Pathwidth），路径宽度为 $d$ 。
将动态规划应用于此路径分解以找到最长的路径，时间是 $O(d!2^{d}n)$ ，其中 $n$ 是图中顶点的数量。

由于输出路径的长度至少与 $d$ 一样大，因此运行时间也受 $O(\ell !2^{\ell }n)$ 的限制，其中 $\ell$ 是最长路径的长度。^[16]

参见

Gallai-Hasse-Roy-Vitaver定理（英语：Gallai–Hasse–Roy–Vitaver theorem），最长路径与图着色的对偶关系
最长无交叉骑士路径（英语：Longest uncrossed knight's path）
盒中蛇（英语：Snake-in-the-box）问题中，超立方体图（英语：Hypercube graph）中的最长诱导路径（英语：Induced path）

参考文献

^ Schrijver, Alexander, Combinatorial Optimization: Polyhedra and Efficiency, Volume 1, Algorithms and Combinatorics 24, Springer: 114, 2003, ISBN 9783540443896 .
^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford, Introduction To Algorithms 2nd, MIT Press: 978, 2001, ISBN 9780262032933 .
^ Lawler, Eugene L., Combinatorial Optimization: Networks and Matroids, Courier Dover Publications: 64, 2001, ISBN 9780486414539 .
^ 王建新; 杨志彪; 陈建二. 最长路径问题研究进展. 计算机科学. 2010-03-02, 36 (12): 1-4,31 [2022-08-15]. doi:10.3969/j.issn.1002-137X.2009.12.001.
^ ^5.0 ^5.1 Sedgewick, Robert; Wayne, Kevin Daniel, Algorithms 4th, Addison-Wesley Professional: 661–666, 2011, ISBN 9780321573513 .
^ Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G., Layered Drawings of Digraphs, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall: 265–302, 1998, ISBN 978-0-13-301615-4 .
^ Bulterman, R.W.; van der Sommen, F.W.; Zwaan, G.; Verhoeff, T.; van Gasteren, A.J.M., On computing a longest path in a tree, Information Processing Letters, 2002, 81 (2): 93–96, doi:10.1016/S0020-0190(01)00198-3 .
^ Uehara, Ryuhei; Uno, Yushi, Efficient algorithms for the longest path problem, Isaac 2004, Lecture Notes in Computer Science, 2004, 3341: 871–883, ISBN 978-3-540-24131-7, doi:10.1007/978-3-540-30551-4_74 .
^ Uehara, Ryuhei; Valiente, Gabriel, Linear structure of bipartite permutation graphs and the longest path problem, Information Processing Letters, 2007, 103 (2): 71–77, CiteSeerX 10.1.1.101.96 , doi:10.1016/j.ipl.2007.02.010 .
^ Takahara, Yoshihiro; Teramoto, Sachio; Uehara, Ryuhei, Longest path problems on Ptolemaic graphs, IEICE Transactions, 2008, 91–D (2): 170–177, doi:10.1093/ietisy/e91-d.2.170  .
^ Ioannidou, Kyriaki; Mertzios, George B.; Nikolopoulos, Stavros D., The longest path problem has a polynomial solution on interval graphs, Algorithmica, 2011, 61 (2): 320–341, CiteSeerX 10.1.1.224.4927 , S2CID 7577817, doi:10.1007/s00453-010-9411-3 .
^ Mertzios, George B.; Bezakova, Ivona, Computing and counting longest paths on circular-arc graphs in polynomial time, Discrete Applied Mathematics, 2014, 164 (2): 383–399, CiteSeerX 10.1.1.224.779 , doi:10.1016/j.dam.2012.08.024 .
^ Mertzios, George B.; Corneil, Derek G., A simple polynomial algorithm for the longest path problem on cocomparability graphs, SIAM Journal on Discrete Mathematics, 2012, 26 (3): 940–963, S2CID 4645245, arXiv:1004.4560 , doi:10.1137/100793529 .
^ Corneil, Derek G.; Krueger, Richard, A unified view of graph searching, SIAM Journal on Discrete Mathematics, 2008, 22 (4): 1259–1276, doi:10.1137/050623498 .
^ Ioannidou, Kyriaki; Nikolopoulos, Stavros D., The longest path problem is polynomial on cocomparability graphs (PDF), Algorithmica, 2011, 65: 177–205 [2022-08-15], CiteSeerX 10.1.1.415.9996 , S2CID 7271040, doi:10.1007/s00453-011-9583-5, （原始内容存档 (PDF)于2022-08-15） .
^ Bodlaender, Hans L., On linear time minor tests with depth-first search, Journal of Algorithms, 1993, 14 (1): 1–23, MR 1199244, doi:10.1006/jagm.1993.1001 . For an earlier FPT algorithm with slightly better dependence on the path length, but worse dependence on the size of the graph, see Monien, B., How to find long paths efficiently, Analysis and design of algorithms for combinatorial problems (Udine, 1982), North-Holland Math. Stud. 109, Amsterdam: North-Holland: 239–254, 1985, ISBN 9780444876997, MR 0808004, doi:10.1016/S0304-0208(08)73110-4 .

外部链接

"Find the Longest Path （页面存档备份，存于互联网档案馆）", song by Dan Barrett

[1] Schrijver, Alexander, Combinatorial Optimization: Polyhedra and Efficiency, Volume 1, Algorithms and Combinatorics 24, Springer: 114, 2003, ISBN 9783540443896 .

[2] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford, Introduction To Algorithms 2nd, MIT Press: 978, 2001, ISBN 9780262032933 .

[3] Lawler, Eugene L., Combinatorial Optimization: Networks and Matroids, Courier Dover Publications: 64, 2001, ISBN 9780486414539 .

[4] 王建新; 杨志彪; 陈建二. 最长路径问题研究进展. 计算机科学. 2010-03-02, 36 (12): 1-4,31 [2022-08-15]. doi:10.3969/j.issn.1002-137X.2009.12.001.

[:0-5] 5.0 ^5.1 Sedgewick, Robert; Wayne, Kevin Daniel, Algorithms 4th, Addison-Wesley Professional: 661–666, 2011, ISBN 9780321573513 .

[6] Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G., Layered Drawings of Digraphs, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall: 265–302, 1998, ISBN 978-0-13-301615-4 .

[7] Bulterman, R.W.; van der Sommen, F.W.; Zwaan, G.; Verhoeff, T.; van Gasteren, A.J.M., On computing a longest path in a tree, Information Processing Letters, 2002, 81 (2): 93–96, doi:10.1016/S0020-0190(01)00198-3 .

[8] Uehara, Ryuhei; Uno, Yushi, Efficient algorithms for the longest path problem, Isaac 2004, Lecture Notes in Computer Science, 2004, 3341: 871–883, ISBN 978-3-540-24131-7, doi:10.1007/978-3-540-30551-4_74 .

[9] Uehara, Ryuhei; Valiente, Gabriel, Linear structure of bipartite permutation graphs and the longest path problem, Information Processing Letters, 2007, 103 (2): 71–77, CiteSeerX 10.1.1.101.96 , doi:10.1016/j.ipl.2007.02.010 .

[10] Takahara, Yoshihiro; Teramoto, Sachio; Uehara, Ryuhei, Longest path problems on Ptolemaic graphs, IEICE Transactions, 2008, 91–D (2): 170–177, doi:10.1093/ietisy/e91-d.2.170  .

[11] Ioannidou, Kyriaki; Mertzios, George B.; Nikolopoulos, Stavros D., The longest path problem has a polynomial solution on interval graphs, Algorithmica, 2011, 61 (2): 320–341, CiteSeerX 10.1.1.224.4927 , S2CID 7577817, doi:10.1007/s00453-010-9411-3 .

[12] Mertzios, George B.; Bezakova, Ivona, Computing and counting longest paths on circular-arc graphs in polynomial time, Discrete Applied Mathematics, 2014, 164 (2): 383–399, CiteSeerX 10.1.1.224.779 , doi:10.1016/j.dam.2012.08.024 .

[13] Mertzios, George B.; Corneil, Derek G., A simple polynomial algorithm for the longest path problem on cocomparability graphs, SIAM Journal on Discrete Mathematics, 2012, 26 (3): 940–963, S2CID 4645245, arXiv:1004.4560 , doi:10.1137/100793529 .

[14] Corneil, Derek G.; Krueger, Richard, A unified view of graph searching, SIAM Journal on Discrete Mathematics, 2008, 22 (4): 1259–1276, doi:10.1137/050623498 .

[15] Ioannidou, Kyriaki; Nikolopoulos, Stavros D., The longest path problem is polynomial on cocomparability graphs (PDF), Algorithmica, 2011, 65: 177–205 [2022-08-15], CiteSeerX 10.1.1.415.9996 , S2CID 7271040, doi:10.1007/s00453-011-9583-5, （原始内容存档 (PDF)于2022-08-15） .

[16] Bodlaender, Hans L., On linear time minor tests with depth-first search, Journal of Algorithms, 1993, 14 (1): 1–23, MR 1199244, doi:10.1006/jagm.1993.1001 . For an earlier FPT algorithm with slightly better dependence on the path length, but worse dependence on the size of the graph, see Monien, B., How to find long paths efficiently, Analysis and design of algorithms for combinatorial problems (Udine, 1982), North-Holland Math. Stud. 109, Amsterdam: North-Holland: 239–254, 1985, ISBN 9780444876997, MR 0808004, doi:10.1016/S0304-0208(08)73110-4 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]