Задача о самом длинном пути ({g;gcg k vgbkb ;lnuukb hrmn)
Задача о самом длинном пути — это задача поиска простого пути максимальной длины в заданном графе. Путь называется простым, если в нём нет повторных вершин. Длина пути может быть измерена либо числом рёбер, либо (в случае взвешенных графов) суммой весов его рёбер. В отличие от задачи кратчайшего пути, которая может быть решена за полиномиальное время на графах без циклов с отрицательным весом, задача нахождения самого длинного пути является 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]. Лучший известный алгоритм аппроксимации полиномиального времени выполнения даёт лишь очень слабую аппроксимацию, [7]. Для любого невозможно аппроксимировать самый длинный путь со множителем, меньшим , если только NP не принадлежит задачам квазиполиномиального детерминированного времени. Однако существует большой разрыв между этим результатом аппроксимируемости и известными алгоритмами аппроксимации для этой задачи[8].
В случае невзвешенных, но ориентированных графов известные сильные результаты аппроксимируемости. Для любого задача не может быть аппроксимирована в пределах , если только не P = NP, и, при сильных теоретических предположениях, задачу нельзя аппроксимировать в пределах [6]. Можно использовать технику цветовой кодировки[англ.] для поиска пути логарифмической длины, если он существует, но эта техника даёт аппроксимационный коэффициент лишь [9].
Параметризованная сложность
[править | править код]Задача поиска самого длинного пути является фиксированно-параметрически разрешимой[англ.], если параметризовать её по длине пути. Например, задача может быть решена за время, линейно зависящее от размера входного графа (но за экспоненциальное время по длине пути), с помощью алгоритма, делающего следующие шаги:
- Осуществляем поиск в глубину по графу. Пусть — глубина результирующего дерева поиска вглубь.
- Используем пути от корня к листам поиска дерева вглубь в порядке, в котором они просматриваются при поиске, в отличие от путевой декомпозиции графа с путевой шириной .
- Используем динамическое программирование к этому разложению на пути для нахождения самого длинного пути за время , где — число вершин графа.
Поскольку выходной путь имеет длину по меньшей мере , время работы также будет ограничено значением , где — длина самого длинного пути[10]. Используя цветовую кодировку, зависимость от длины пути может быть сведена к одиночно экспоненциальной[11][12][13]. Похожая техника динамического программирования показывает, что задача нахождения самого длинного пути является также фиксированно-параметрически разрешимой по древесной ширине графа.
Для графов с ограниченной кликовой шириной задачу о самом длинном пути можно решить за полиномиальное время с помощью алгоритма динамического программирования. Однако степень полинома зависит от кликовой ширины графа, так что эти алгоритмы не являются фиксированно-параметрически разрешимыми. Задача нахождения самого длинного пути, параметризованная по ширине клик, является трудной для класса парметризованной сложности[англ.] , что говорит о том, что вряд ли существует фиксированно-параметрически разрешимый алгоритм[14].
Специальные случаи графов
[править | править код]Задачу о самом длинном пути можно решить за полиномиальное время на дополнениях графов сравнимости[15]. Её можно решить также за полиномиальное время на любом классе графов с ограниченной древесной шириной или ограниченной кликовой шириной, таком как дистанционно-наследуемые графы. Однако задача является NP-трудной, даже если ограничимся расщепляемыми графами, круговыми графами или планарными графами[16].
См. также
[править | править код]- Теорема Галлаи – Хассе – Роя – Витавера, двойственность самого длинного пути и раскраски графов
- Задача о ходе коня
- Задача о змее в коробке, самый длинный порождённый путь в графе гиперкуба
Примечания
[править | править код]- ↑ Schrijver, 2003, с. 114.
- ↑ Cormen, Leiserson, Rivest, Stein, 2001, с. 978.
- ↑ Lawler, 2001, с. 64.
- ↑ 1 2 3 Sedgewick, Wayne, 2011, с. 661–666.
- ↑ Di Battista, Eades, Tamassia, Tollis, 1998, с. 265–302.
- ↑ 1 2 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*(2k) 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)
Для улучшения этой статьи желательно:
|