“Longest path problem”的意思、由来-开放百科全书

In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called simple if it does not have any repeated vertices; the length of a path may either be measured by its number of edges, or (in weighted graphs) by the sum of the weights of its edges. In contrast to the shortest path problem, which can be solved in polynomial time in graphs without negative-weight cycles, the longest path problem is NP-complete, meaning that it cannot be solved in polynomial time for arbitrary graphs unless P = NP. Stronger hardness results are also known showing that it is difficult to approximate. However, it has a linear time solution for directed acyclic graphs, which has important applications in finding the critical path in scheduling problems.

NP-hardness

The NP-hardness of the unweighted longest path problem can be shown using a reduction from the Hamiltonian path problem: a graph G has a Hamiltonian path if and only if its longest path has length n − 1, where n is the number of vertices in G. Because the Hamiltonian path problem is NP-complete, this reduction shows that the decision version of the longest path problem is also NP-complete. In this decision problem, the input is a graph G and a number k; the desired output is "yes" if G contains a path of k or more edges, and no otherwise.^[1]

If the longest path problem could be solved in polynomial time, it could be used to solve this decision problem, by finding a longest path and then comparing its length to the number k. Therefore, the longest path problem is NP-hard. The question "does there exist a simple path in a given graph with at least k edges" is NP-complete.^[2]

In weighted complete graphs with non-negative edge weights, the weighted longest path problem is the same as the Travelling salesman path problem, because the longest path always includes all vertices.^[3]

Acyclic graphs and critical paths

A longest path between two given vertices s and t in a weighted graph G is the same thing as a shortest path in a graph −G derived from G by changing every weight to its negation. Therefore, if shortest paths can be found in −G, then longest paths can also be found in G.^[4]

For most graphs, this transformation is not useful because it creates cycles of negative length in −G. But if G is a directed acyclic graph, then no negative cycles can be created, and a longest path in G can be found in linear time by applying a linear time algorithm for shortest paths in −G, which is also a directed acyclic graph.^[4] For instance, for each vertex v in a given DAG, the length of the longest path ending at v may be obtained by the following steps:

Once this has been done, the longest path in the whole DAG may be obtained by starting at the vertex v with the largest recorded value, then repeatedly stepping backwards to its incoming neighbor with the largest recorded value, and reversing the sequence of vertices found in this way.

The critical path method for scheduling a set of activities involves the construction of a directed acyclic graph in which the vertices represent project milestones and the edges represent activities that must be performed after one milestone and before another; each edge is weighted by an estimate of the amount of time the corresponding activity will take to complete. In such a graph, the longest path from the first milestone to the last one is the critical path, which describes the total time for completing the project.^[4]

Longest paths of directed acyclic graphs may also be applied in layered graph drawing: assigning each vertex v of a directed acyclic graph G to the layer whose number is the length of the longest path ending at v results in a layer assignment for G with the minimum possible number of layers.^[5]

Approximation

The best polynomial time approximation algorithm known for this case achieves only a very weak approximation ratio,

.^[7] For all

, it is not possible to approximate the longest path to within a factor of

unless NP is contained within quasi-polynomial deterministic time; however, there is a big gap between this inapproximability result and the known approximation algorithms for this problem.^[8]

In the case of unweighted but directed graphs, strong inapproximability results are known. For every

the problem cannot be approximated to within a factor of

unless P = NP, and with stronger complexity-theoretic assumptions it cannot be approximated to within a factor of

.^[6] The color-coding technique can be used to find paths of logarithmic length, if they exist, but this gives an approximation ratio of only

.^[9]

Parameterized complexity

The longest path problem is fixed-parameter tractable when parameterized by the length of the path. For instance, it can be solved in time linear in the size of the input graph (but exponential in the length of the path), by an algorithm that performs the following steps:

Since the output path has length at least as large as

, the running time is also bounded by

, where

is the length of the longest path.^[10] Using color-coding, the dependence on path length can be reduced to singly exponential.^[9]^[11]^[12]^[13] A similar dynamic programming technique shows that the longest path problem is also fixed-parameter tractable when parameterized by the treewidth of the graph.

For graphs of bounded clique-width, the longest path can also be solved by a polynomial time dynamic programming algorithm. However, the exponent of the polynomial depends on the clique-width of the graph, so this algorithms is not fixed-parameter tractable. The longest path problem, parameterized by clique-width, is hard for the parameterized complexity class

, showing that a fixed-parameter tractable algorithm is unlikely to exist.^[14]

Special classes of graphs

A linear-time algorithm for finding a longest path in a tree was proposed by Dijkstra in 1960's, while a formal proof of this algorithm was published in 2002.^[15]

Furthermore, a longest path can be computed in polynomial time on weighted trees, on block graphs, on cacti,^[16]

For the class of interval graphs, an

-time algorithm is known, which uses a dynamic programming approach.^[19]

This dynamic programming approach has been exploited to obtain polynomial-time algorithms on the greater classes of circular-arc graphs^[20]

and of co-comparability graphs (i.e. of the complements of comparability graphs, which also contain permutation graphs),^[21]

both having the same running time

. The latter algorithm is based on special properties of the Lexicographic Depth First Search (LDFS) vertex ordering^[22]

of co-comparability graphs. For co-comparability graphs also an alternative polynomial-time algorithm with higher running time

is known, which is based on the Hasse diagram of the partially ordered set defined by the complement of the input co-comparability graph.^[23]

Furthermore, the longest path problem is solvable in polynomial time on any class of graphs with bounded treewidth or bounded clique-width, such as the distance-hereditary graphs. Finally, it is clearly NP-hard on all graph classes on which the Hamiltonian path problem is NP-hard, such as on split graphs, circle graphs, and planar graphs.

See also

References

1. ^{{citation|title=Combinatorial Optimization: Polyhedra and Efficiency, Volume 1|volume=24|series=Algorithms and Combinatorics|first=Alexander|last=Schrijver|authorlink=Alexander Schrijver|publisher=Springer|year=2003|isbn=9783540443896|page=114|url=https://books.google.com/books?id=mqGeSQ6dJycC&pg=PA114}}.
2. ^{{citation|title=Introduction To Algorithms|first1=Thomas H.|last1=Cormen|author1-link=Thomas H. Cormen|first2=Charles E.|last2=Leiserson|author2-link=Charles E. Leiserson|first3=Ronald L.|last3=Rivest|author3-link=Ron Rivest|first4=Clifford|last4=Stein|author4-link=Clifford Stein|edition=2nd|publisher=MIT Press|year=2001|isbn=9780262032933|url=https://books.google.com/books?id=NLngYyWFl_YC&pg=PA978|page=978}}.
3. ^{{citation|title=Combinatorial Optimization: Networks and Matroids|first=Eugene L.|last=Lawler|authorlink=Eugene Lawler|publisher=Courier Dover Publications|year=2001|isbn=9780486414539|page=64|url=https://books.google.com/books?id=m4MvtFenVjEC&pg=PA64}}.
4. ^¹²{{citation|title=Algorithms|first1=Robert|last1=Sedgewick|author1-link=Robert Sedgewick (computer scientist)|first2=Kevin Daniel|last2=Wayne|edition=4th|publisher=Addison-Wesley Professional|year=2011|isbn=9780321573513|pages=661–666|url=https://books.google.com/books?id=idUdqdDXqnAC&pg=PA661}}.
5. ^{{citation | last1 = Di Battista | first1 = Giuseppe | last2 = Eades | first2 = Peter | author2-link = Peter Eades | last3 = Tamassia | first3 = Roberto | author3-link = Roberto Tamassia | last4 = Tollis | first4 = Ioannis G. | contribution = Layered Drawings of Digraphs | isbn = 978-0-13-301615-4 | pages = 265–302 | publisher = Prentice Hall | title = Graph Drawing: Algorithms for the Visualization of Graphs | year = 1998}}.
6. ^¹{{citation | last1 = Björklund | first1 = Andreas | last2 = Husfeldt | first2 = Thore | last3 = Khanna | first3 = Sanjeev | contribution = Approximating longest directed paths and cycles | location = Berlin | mr = 2160935 | pages = 222–233 | publisher = Springer-Verlag | series = Lecture Notes in Computer Science | title = Proc. Int. Coll. Automata, Languages and Programming (ICALP 2004) | volume = 3142 | year = 2004}}.
7. ^{{citation | last1 = Gabow | first1 = Harold N. | last2 = Nie | first2 = Shuxin | contribution = Finding long paths, cycles and circuits | doi = 10.1007/978-3-540-92182-0_66 | location = Berlin | mr = 2539968 | pages = 752–763 | publisher = Springer | series = Lecture Notes in Computer Science | title = International Symposium on Algorithms and Computation | volume = 5369 | year = 2008| isbn = 978-3-540-92181-3 }}. For earlier work with even weaker approximation bounds, see {{citation | last = Gabow | first = Harold N. | doi = 10.1137/S0097539704445366 | issue = 6 | journal = SIAM Journal on Computing | mr = 2299418 | pages = 1648–1671 | title = Finding paths and cycles of superpolylogarithmic length | url = http://www.cs.colorado.edu/~hal/u.pdf | volume = 36 | year = 2007}} and {{citation | last1 = Björklund | first1 = Andreas | last2 = Husfeldt | first2 = Thore | doi = 10.1137/S0097539702416761 | issue = 6 | journal = SIAM Journal on Computing | mr = 2034242 | pages = 1395–1402 | title = Finding a path of superlogarithmic length | volume = 32 | year = 2003| url = http://lup.lub.lu.se/record/526604 }}.
8. ^{{citation | last1 = Karger | first1 = David | author1-link = David Karger | last2 = Motwani | first2 = Rajeev | author2-link = Rajeev Motwani | last3 = Ramkumar | first3 = G. D. S. | doi = 10.1007/BF02523689 | issue = 1 | journal = Algorithmica | mr = 1432030 | pages = 82–98 | title = On approximating the longest path in a graph | volume = 18 | year = 1997}}.
9. ^¹{{citation | last1 = Alon | first1 = Noga | author1-link = Noga Alon | last2 = Yuster | first2 = Raphael | last3 = Zwick | first3 = Uri | author3-link = Uri Zwick | doi = 10.1145/210332.210337 | issue = 4 | journal = Journal of the ACM | mr = 1411787 | pages = 844–856 | title = Color-coding | volume = 42 | year = 1995}}.
10. ^{{citation | last = Bodlaender | first = Hans L. | authorlink = Hans L. Bodlaender | doi = 10.1006/jagm.1993.1001 | issue = 1 | journal = Journal of Algorithms | mr = 1199244 | pages = 1–23 | title = On linear time minor tests with depth-first search | volume = 14 | year = 1993}}. For an earlier FPT algorithm with slightly better dependence on the path length, but worse dependence on the size of the graph, see {{citation | last = Monien | first = B. | contribution = How to find long paths efficiently | doi = 10.1016/S0304-0208(08)73110-4 | location = Amsterdam | mr = 808004 | pages = 239–254 | publisher = North-Holland | series = North-Holland Math. Stud. | title = Analysis and design of algorithms for combinatorial problems (Udine, 1982) | volume = 109 | year = 1985| isbn = 9780444876997 }}.
11. ^{{citation | last1 = Chen | first1 = Jianer | last2 = Lu | first2 = Songjian | last3 = Sze | first3 = Sing-Hoi | last4 = Zhang | first4 = Fenghui | contribution = Improved algorithms for path, matching, and packing problems | pages = 298–307 | title = Proc. 18th ACM-SIAM Symposium on Discrete algorithms (SODA '07) | url = http://faculty.cse.tamu.edu/shsze/papers/kpath.pdf | year = 2007}}.
12. ^{{citation | last = Koutis | first = Ioannis | contribution = Faster algebraic algorithms for path and packing problems | url = http://ccom.uprrp.edu/~ikoutis/papers/MultilinearDetection.pdf | doi = 10.1007/978-3-540-70575-8_47 | location = Berlin | mr = 2500302 | pages = 575–586 | publisher = Springer | series = Lecture Notes in Computer Science | title = International Colloquium on Automata, Languages and Programming | volume = 5125 | year = 2008| isbn = 978-3-540-70574-1 | citeseerx = 10.1.1.141.6899 }}.
13. ^{{citation | last = Williams | first = Ryan | authorlink = Ryan Williams (computer scientist) | arxiv = 0807.3026 | doi = 10.1016/j.ipl.2008.11.004 | issue = 6 | journal = Information Processing Letters | mr = 2493730 | pages = 315–318 | title = Finding paths of length k in O*(2^k) time | volume = 109 | year = 2009}}.
14. ^{{citation | last1 = Fomin | first1 = Fedor V. | last2 = Golovach | first2 = Petr A. | last3 = Lokshtanov | first3 = Daniel | last4 = Saurabh | first4 = Saket | contribution = Clique-width: on the price of generality | pages = 825–834 | title = Proc. 20th ACM-SIAM Symposium on Discrete Algorithms (SODA '09) | url = https://www.siam.org/proceedings/soda/2009/SODA09_090_fominf.pdf | year = 2009}}.
15. ^{{citation | last1 = Bulterman | first1 = R.W. | last2 = van der Sommen | first2 = F.W. | last3 = Zwaan | first3 = G. | last4 = Verhoeff | first4 = T. | last5 = van Gasteren | first5 = A.J.M. | doi = 10.1016/S0020-0190(01)00198-3 | journal = Information Processing Letters | title = On computing a longest path in a tree | url = http://www.sciencedirect.com/science/article/pii/S0020019001001983 | issue = 2 | pages = 93–96 | volume = 81 | year = 2002}}.
16. ^{{citation | last1 = Uehara | first1 = Ryuhei | last2 = Uno | first2 = Yushi | journal = Isaac 2004 | volume = 3341 | title = Efficient algorithms for the longest path problem | pages = 871–883 | year = 2004| doi = 10.1007/978-3-540-30551-4_74 | series = Lecture Notes in Computer Science | isbn = 978-3-540-24131-7 }}.
17. ^{{citation | last1 = Uehara | first1 = Ryuhei | last2 = Valiente | first2 = Gabriel | doi = 10.1016/j.ipl.2007.02.010 | journal = Information Processing Letters | title = Linear structure of bipartite permutation graphs and the longest path problem | url = http://www.sciencedirect.com/science/article/pii/S0020019007000464 | issue = 2 | pages = 71–77 | volume = 103 | year = 2007| citeseerx = 10.1.1.101.96 }}.
18. ^{{citation | last1 = Takahara | first1 = Yoshihiro | last2 = Teramoto | first2 = Sachio | last3 = Uehara | first3 = Ryuhei | journal = IEICE Transactions | title = Longest path problems on Ptolemaic graphs | pages = 170–177 | volume = 91-D | issue = 2 | year = 2008| doi = 10.1093/ietisy/e91-d.2.170 }}.
19. ^{{citation | last1 = Ioannidou | first1 = Kyriaki | last2 = Mertzios | first2 = George B. | last3 = Nikolopoulos | first3 = Stavros D. | doi = 10.1007/s00453-010-9411-3 | journal = Algorithmica | title = The longest path problem has a polynomial solution on interval graphs | issue = 2 | pages = 320–341 | volume = 61 | year = 2011| citeseerx = 10.1.1.224.4927 }}.
20. ^{{citation | last1 = Mertzios | first1 = George B. | last2 = Bezakova | first2 = Ivona | doi = 10.1016/j.dam.2012.08.024 | journal = Discrete Applied Mathematics | title = Computing and counting longest paths on circular-arc graphs in polynomial time | url = http://www.sciencedirect.com/science/article/pii/S0166218X12003241 | issue = 2 | pages = 383–399 | volume = 164 | year = 2014| citeseerx = 10.1.1.224.779 }}.
21. ^{{citation | last1 = Mertzios | first1 = George B. | last2 = Corneil | first2 = Derek G. | doi = 10.1137/100793529 | journal = SIAM Journal on Discrete Mathematics | title = A simple polynomial algorithm for the longest path problem on cocomparability graphs | issue = 3 | pages = 940–963 | volume = 26 | year = 2012| arxiv = 1004.4560 }}.
22. ^{{citation | last1 = Corneil | first1 = Derek G. | last2 = Krueger | first2 = Richard | doi = 10.1137/050623498 | journal = SIAM Journal on Discrete Mathematics | title = A unified view of graph searching | issue = 4 | pages = 1259–1276 | volume = 22 | year = 2008}}.
23. ^{{citation | last1 = Ioannidou | first1 = Kyriaki | last2 = Nikolopoulos | first2 = Stavros D. | doi = 10.1007/s00453-011-9583-5 | journal = Algorithmica | volume = 65 | pages = 177–205 | title = The longest path problem is polynomial on cocomparability graphs | url = http://www.cs.uoi.gr/~stavros/J-Papers/J-2012-ALGO.pdf | year = 2011| citeseerx = 10.1.1.415.9996 }}.