Википедия

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

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

NP-трудность править

NP-трудность невзвешенной задачи поиска самого длинного пути можно показать, сведя задачу к поиску гамильтонова пути[en] — граф 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]. Лучший известный алгоритм аппроксимации полиномиального времени выполнения даёт лишь очень слабую аппроксимацию,   [7]. Для любого   невозможно аппроксимировать самый длинный путь со множителем, меньшим  , если только NP не принадлежит задачам квазиполиномиального детерминированного времени. Однако существует большой разрыв между этим результатом аппроксимируемости и известными алгоритмами аппроксимации для этой задачи[8].

В случае невзвешенных, но ориентированных графов известные сильные результаты аппроксимируемости. Для любого   задача не может быть аппроксимирована в пределах  , если только не P = NP, и, при сильных теоретических предположениях, задачу нельзя аппроксимировать в пределах  [6]. Можно использовать технику цветовой кодировки[en] для поиска пути логарифмической длины, если он существует, но эта техника даёт аппроксимационный коэффициент лишь  [9].

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

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

  1. Осуществляем поиск в глубину по графу. Пусть   — глубина результирующего дерева поиска вглубь.
  2. Используем пути от корня к листам поиска дерева вглубь в порядке, в котором они просматриваются при поиске, в отличие от путевой декомпозиции графа с путевой шириной  .
  3. Используем динамическое программирование к этому разложению на пути для нахождения самого длинного пути за время  , где   — число вершин графа.

Поскольку выходной путь имеет длину по меньшей мере  , время работы также будет ограничено значением  , где   — длина самого длинного пути[10]. Используя цветовую кодировку, зависимость от длины пути может быть сведена к одиночно экспоненциальной[11][12][13]. Похожая техника динамического программирования показывает, что задача нахождения самого длинного пути является также фиксированно-параметрически разрешимой по древесной ширине графа.

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

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

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

См. также править

Примечания править

  1. ↑ Schrijver, 2003, с. 114.
  2. ↑ Cormen, Leiserson, Rivest, Stein, 2001, с. 978.
  3. ↑ Lawler, 2001, с. 64.
  4. ↑ 1 2 3 Sedgewick, Wayne, 2011, с. 661–666.
  5. ↑ Di Battista, Eades, Tamassia, Tollis, 1998, с. 265–302.
  6. ↑ 1 2 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*(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.

Ссылки править

Источник — https://ru.wikipedia.org/w/index.php?title=Задача_о_самом_длинном_пути&oldid=126477210