Задача о самом длинном пути

Задача о самом длинном пути — это задача поиска простого пути максимальной длины в заданном графе. Путь называется простым, если в нём нет повторных вершин. Длина пути может быть измерена либо числом рёбер, либо (в случае взвешенных графов) суммой весов его рёбер. В отличие от задачи кратчайшего пути, которая может быть решена за полиномиальное время на графах без циклов с отрицательным весом, задача нахождения самого длинного пути является NP-трудной и не может быть решена за полиномиальное время для произвольных графов, если только не P = NP. Принадлежность более тяжелому классу сложности также означает, что задачу трудно аппроксимировать. Однако задача решается за линейное время на ориентированных ациклических графах, которые имеют важное применение в задачах нахождения критического пути в задачах планирования.

NP-трудность

NP-трудность невзвешенной задачи поиска самого длинного пути можно показать, сведя задачу к поиску гамильтонова пути^[англ.] — граф G имеет гамильтонов путь тогда и только тогда, когда самый длинный путь в нём имеет длину n − 1, где n — число вершин графа G. Поскольку задача поиска гамильтонова пути является NP-полной, это сведение показывает, что задачи поиска самого длинного пути в варианте разрешимости также NP-полна. В этой задаче разрешимости входом является граф G и число k. Ожидается выход "да", если G содержит путь с k и больше дугами, или нет в противном случае[1].

Если бы задача поиска самого длинного пути могла быть решена за полиномиальное время, она могла бы быть использована для решения этой задачи разрешимости путём нахождения самого длинного пути и сравнения длины полученного пути с числом k. Таким образом, задача поиска самого длинного пути является NP-трудной. Она не является NP-полной, поскольку она не является задачей разрешимости[2].

Во взвешенных полных графах с неотрицательными весами рёбер задача поиска взвешенного самого длинного пути является той же самой задачей, что и задача коммивояжёра, поскольку самый длинный путь всегда включает все вершины этой задачи[3].

Ацикличные графы и критические пути

Самый длинный путь A между двумя заданными вершинами s и t во взвешенном графе G — это то же самое, что и кратчайший путь в графе −G, полученном из G путём замены всех весов на веса с обратным знаком. Таким образом, если кратчайший путь можно найти в −G, то можно найти и самый длинный путь в G[4].

Для большинства графов такое преобразование бесполезно, поскольку создаёт циклы отрицательной длины в −G. Но если G является ориентированным ациклическим графом, невозможно создать отрицательный цикл и самый длинный путь в G может быть найден за линейное время, применив алгоритм поиска кратчайшего пути в −G (тоже ориентированный ациклический граф), который работает за линейное время[4]. Например, для любой вершины v в ориентированном ациклическом графе длина самого длинного пути, заканчивающегося в v, может быть получена выполнением следующих шагов:

1. Осуществляем топологическую сортировку заданного ориентированного ациклического графа (ОАГ).
2. Для каждой вершины v ОАГ в топологической сортировке вычисляем длину самого длинного пути, завершающегося в вершине v путём просмотра входящих дуг от соседей и добавления единички к максимальной длине в записях этих соседей. Если v не имеет входящих дуг, присваиваем длину самого длинного пути, кончающегося в v, нулю.

Когда это будет сделано, самый длинный путь во всём графе можно получить, начав с вершины v с самым большим записанным значением и проходя в обратном порядке, выбирая входящую дугу, у которой запись в начальной вершине имеет наибольшее значение.

Метод критического пути для планирования набора работ использует построение ориентированного ацикличного графа, в котором вершины представляют узловые события проекта, а дуги представляют работы, которые должны быть выполнены до узлового события и после него. Каждой дуге присваивается вес, равный оценочному времени выполнения работы. В таком графе самый длинный путь от первого узлового события до последнего является критическим путём, который определяет полное время завершения проекта[4].

Самый длинный путь ориентированных ацикличных графов можно применить также для послойного рисования графов — располагаем каждую вершину v ориентированного ацикличного графа G на уровне, номер которого соответствует длине самого длинного пути, заканчивающегося в v. В результате получим расположение вершин по уровням, при котором число уровней будет минимальным[5].

Приближение

Бьёрклунд, Хасфелдт и Канна писали, что задача поиска самого длинного пути в невзвешенном неориентированном графе является «печально известной по сложности понимания её трудности аппроксимации»[6]. Лучший известный алгоритм аппроксимации полиномиального времени выполнения даёт лишь очень слабую аппроксимацию, ${\displaystyle n/\exp(\Omega ({\sqrt {\log n}}))}$ [7]. Для любого ${\displaystyle \epsilon >0}$ невозможно аппроксимировать самый длинный путь со множителем, меньшим ${\displaystyle 2^{(\log n)^{1-\epsilon }}}$, если только NP не принадлежит задачам квазиполиномиального детерминированного времени. Однако существует большой разрыв между этим результатом аппроксимируемости и известными алгоритмами аппроксимации для этой задачи[8].

В случае невзвешенных, но ориентированных графов известные сильные результаты аппроксимируемости. Для любого ${\displaystyle \epsilon >0}$ задача не может быть аппроксимирована в пределах ${\displaystyle n^{1-\epsilon }}$, если только не P = NP, и, при сильных теоретических предположениях, задачу нельзя аппроксимировать в пределах ${\displaystyle n/\log ^{2+\epsilon }n}$[6]. Можно использовать технику цветовой кодировки^[англ.] для поиска пути логарифмической длины, если он существует, но эта техника даёт аппроксимационный коэффициент лишь ${\displaystyle O(n/\log n)}$[9].

Параметризованная сложность

Задача поиска самого длинного пути является фиксированно-параметрически разрешимой^[англ.], если параметризовать её по длине пути. Например, задача может быть решена за время, линейно зависящее от размера входного графа (но за экспоненциальное время по длине пути), с помощью алгоритма, делающего следующие шаги:

1. Осуществляем поиск в глубину по графу. Пусть ${\displaystyle d}$ — глубина результирующего дерева поиска вглубь.
2. Используем пути от корня к листам поиска дерева вглубь в порядке, в котором они просматриваются при поиске, в отличие от путевой декомпозиции графа с путевой шириной ${\displaystyle d}$.
3. Используем динамическое программирование к этому разложению на пути для нахождения самого длинного пути за время ${\displaystyle O(d!2^{d}n)}$, где ${\displaystyle n}$ — число вершин графа.

Поскольку выходной путь имеет длину по меньшей мере ${\displaystyle d}$, время работы также будет ограничено значением ${\displaystyle O(\ell !2^{\ell }n)}$, где ${\displaystyle \ell }$ — длина самого длинного пути[10]. Используя цветовую кодировку, зависимость от длины пути может быть сведена к одиночно экспоненциальной[11][12][13]. Похожая техника динамического программирования показывает, что задача нахождения самого длинного пути является также фиксированно-параметрически разрешимой по древесной ширине графа.

Для графов с ограниченной кликовой шириной задачу о самом длинном пути можно решить за полиномиальное время с помощью алгоритма динамического программирования. Однако степень полинома зависит от кликовой ширины графа, так что эти алгоритмы не являются фиксированно-параметрически разрешимыми. Задача нахождения самого длинного пути, параметризованная по ширине клик, является трудной для класса парметризованной сложности^[англ.] ${\displaystyle W[1]}$, что говорит о том, что вряд ли существует фиксированно-параметрически разрешимый алгоритм[14].

Специальные случаи графов

Задачу о самом длинном пути можно решить за полиномиальное время на дополнениях графов сравнимости[15]. Её можно решить также за полиномиальное время на любом классе графов с ограниченной древесной шириной или ограниченной кликовой шириной, таком как дистанционно-наследуемые графы. Однако задача является NP-трудной, даже если ограничимся расщепляемыми графами, круговыми графами или планарными графами[16].

См. также

• Теорема Галлаи – Хассе – Роя – Витавера, двойственность самого длинного пути и раскраски графов
• Задача о ходе коня
• Задача о змее в коробке, самый длинный порождённый путь в графе гиперкуба

Примечания

1. Schrijver, 2003, с. 114.
2. Cormen, Leiserson, Rivest, Stein, 2001, с. 978.
3. Lawler, 2001, с. 64.
4. Sedgewick, Wayne, 2011, с. 661–666.
5. Di Battista, Eades, Tamassia, Tollis, 1998, с. 265–302.
6. Björklund, Husfeldt, Khanna, 2004, с. 222–233.
7. (Gabow, Nie 2008). Для более ранних работ даже с более слабой аппроксимацией см. статьи Габова (Gabow 2007) и Бьёрклунда и Хасфелдта (Björklund, Husfeldt 2003).
8. Karger, Motwani, Ramkumar, 1997, с. 82–98.
9. Alon, Yuster, Zwick, 1995.
10. (Bodlaender 1993). Для более раннего фиксированно-параметрически разрешимого алгоритма с чуть лучшей зависимостью от длины пути, но с худшей зависимостью от длины графа, см. статью (Monien 1985).
11. Chen, Lu, Sze, Zhang, 2007, с. 298-307.
12. Koutis, 2008, с. 575-586.
13. Williams, 2009, с. 315-318.
14. Fomin, Golovach, Lokshtanov, Saurabh, 2009, с. 825–834.
15. (Ioannidou, Nikolopoulos 2011). Для более ранних работ на более ограниченных классах см. статьи (Ioannidou, Mertzios, Nikolopoulos 2011) и (Uehara, Valiente 2007).
16. Ioannidou, Mertzios, Nikolopoulos, 2011.

Литература

• Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. — Springer, 2003. — Т. 24. — (Algorithms and Combinatorics). — ISBN 9783540443896.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction To Algorithms. — MIT Press, 2001. — ISBN 9780262032933.
• Robert Sedgewick, Kevin Daniel Wayne. Algorithms. — Addison-Wesley Professional, 2011. — С. 661—666. — ISBN 9780321573513.
• Eugene L. Lawler. Combinatorial Optimization: Networks and Matroids. — Courier Dover Publications, 2001. — С. 64. — ISBN 9780486414539.
• Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. — Prentice Hall, 1998. — С. 265—302. — ISBN 978-0-13-301615-4.
• Andreas Björklund, Thore Husfeldt, Sanjeev Khanna. Proc. Int. Coll. Automata, Languages and Programming (ICALP 2004). — Berlin: Springer-Verlag, 2004. — Т. 3142. — С. 222—233. — (Lecture Notes in Computer Science).
• Harold N. Gabow, Shuxin Nie. International Symposium on Algorithms and Computation. — Berlin: Springer, 2008. — Т. 5369. — С. 752—763. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-540-92182-0_66.
• Harold N. Gabow. Finding paths and cycles of superpolylogarithmic length // SIAM Journal on Computing. — 2007. — Т. 36, вып. 6. — С. 1648—1671. — doi:10.1137/S0097539704445366.
• Andreas Björklund, Thore Husfeldt. Finding a path of superlogarithmic length // SIAM Journal on Computing. — 2003. — Т. 32, вып. 6. — С. 1395—1402. — doi:10.1137/S0097539702416761.
• David Karger, Rajeev Motwani, G. D. S. Ramkumar. On approximating the longest path in a graph // Algorithmica. — 1997. — Т. 18, вып. 1. — С. 82—98. — doi:10.1007/BF02523689.
• Noga Alon, Raphael Yuster, Uri Zwick. Color-coding // Journal of the ACM. — 1995. — Т. 42, вып. 4. — С. 844—856. — doi:10.1145/210332.210337.
• Hans L. Bodlaender. On linear time minor tests with depth-first search // Journal of Algorithms. — 1993. — Т. 14, вып. 1. — С. 1—23. — doi:10.1006/jagm.1993.1001.
• B. Monien. Analysis and design of algorithms for combinatorial problems (Udine, 1982). — Amsterdam: North-Holland, 1985. — Т. 109. — С. 239—254. — (North-Holland Math. Stud.). — doi:10.1016/S0304-0208(08)73110-4.
• Jianer Chen, Songjian Lu, Sing-Hoi Sze, Fenghui Zhang. Proc. 18th ACM-SIAM Symposium on Discrete algorithms (SODA '07). — 2007. — С. 298—307.
• Ioannis Koutis. International Colloquium on Automata, Languages and Programming. — Berlin: Springer, 2008. — Т. 5125. — С. 575—586. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-540-70575-8_47.
• Ryan Williams. Finding paths of length k in O*(2^k) time // Information Processing Letters. — 2009. — Т. 109, вып. 6. — С. 315—318. — doi:10.1016/j.ipl.2008.11.004. — arXiv:0807.3026.
• Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh. Proc. 20th ACM-SIAM Symposium on Discrete Algorithms (SODA '09). — 2009. — С. 825—834.
• Kyriaki Ioannidou, Stavros D. Nikolopoulos. The longest path problem is polynomial on cocomparability graphs // Algorithmica. — 2011. — doi:10.1007/s00453-011-9583-5.
• Kyriaki Ioannidou, George B. Mertzios, Stavros D. Nikolopoulos. The longest path problem has a polynomial solution on interval graphs // Algorithmica. — 2011. — Т. 61, вып. 2. — С. 320—341. — doi:10.1007/s00453-010-9411-3.
• Ryuhei Uehara, Gabriel Valiente. Linear structure of bipartite permutation graphs and the longest path problem // Information Processing Letters. — 2007. — Т. 103, вып. 2. — С. 71—77. — doi:10.1016/j.ipl.2007.02.010.
• Метод нечёткого критического пути / Акимов В. А., Балашов В. Г., Заложнев А. Ю. // Управление большими системами. Выпуск 3. М.: ИПУ РАН, 2003. С. 5-10.

Ссылки

• "Find the Longest Path", песня Дана Барретта (Dan Barrett)