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

Задача о самом длинном пути — это задача поиска простого пути максимальной длины в заданном графе. Путь называется простым, если в нём нет повторных вершин. Длина пути может быть измерена либо числом рёбер, либо (в случае взвешенных графов) суммой весов его рёбер. В отличие от задачи кратчайшего пути, которая может быть решена за полиномиальное время на графах без циклов с отрицательным весом, задача нахождения самого длинного пути является 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, может быть получена выполнением следующих шагов:

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

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

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

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

Приближение

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

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

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

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

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

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

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

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

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

См. также

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

Примечания

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

[_975ee8e4e50c4e54-1] Schrijver, 2003, с. 114.

[_f545bd1bb365da5e-2] Cormen, Leiserson, Rivest, Stein, 2001, с. 978.

[_16faaf0e2d0e9a03-3] Lawler, 2001, с. 64.

[_8b81aa1d564fe15f-4] ¹ ² ³ Sedgewick, Wayne, 2011, с. 661–666.

[_7b7aef4036c84cfa-5] Di Battista, Eades, Tamassia, Tollis, 1998, с. 265–302.

[_00ee6f8f4694d2eb-6] ¹ ² Björklund, Husfeldt, Khanna, 2004, с. 222–233.

[7] (Gabow, Nie 2008). Для более ранних работ даже с более слабой аппроксимацией см. статьи Габова (Gabow 2007) и Бьёрклунда и Хасфелдта (Björklund, Husfeldt 2003).

[_e15a0ad36dd30520-8] Karger, Motwani, Ramkumar, 1997, с. 82–98.

[_5282576047367d59-9] Alon, Yuster, Zwick, 1995.

[10] (Bodlaender 1993). Для более раннего фиксированно-параметрически разрешимого алгоритма с чуть лучшей зависимостью от длины пути, но с худшей зависимостью от длины графа, см. статью (Monien 1985).

[_8a6249ae21a85735-11] Chen, Lu, Sze, Zhang, 2007, с. 298-307.

[_f41278a26cc54d49-12] Koutis, 2008, с. 575-586.

[_660244223351f0d2-13] Williams, 2009, с. 315-318.

[_bf1ba6c72d644a7a-14] Fomin, Golovach, Lokshtanov, Saurabh, 2009, с. 825–834.

[15] (Ioannidou, Nikolopoulos 2011). Для более ранних работ на более ограниченных классах см. статьи (Ioannidou, Mertzios, Nikolopoulos 2011) и (Uehara, Valiente 2007).

[_891fd47a6827b856-16] Ioannidou, Mertzios, Nikolopoulos, 2011.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]