Задача про найдовший шлях

Завдання про найдовший шлях — це задача пошуку простого шляху найбільшої довжини в заданому графі. Шлях називається простим, якщо в ньому немає повторних вершин. Довжину шляху можна виміряти або числом ребер, або (в разі зважених графів) сумою ваг його ребер. На відміну від задачі про найкоротший шлях, яку на графах без циклів з від'ємною вагою можна розв'язати за поліноміальний час, задача пошуку найдовшого шляху є NP-складною і не може бути розв'язаною за поліноміальний час для довільного графа, якщо не P = NP. Належність до вищого класу складності також означає, що задачу складно апроксимувати. Однак задача розв'язується за лінійний час на орієнтованих ациклічних графах, які мають важливе застосування в задачах знаходження критичного шляху в задачах планування.

NP-складність

NP-складність незваженої задачі пошуку найдовшого шляху можна показати, звівши задачу до пошуку гамільтонового шляху — граф G має гамільтонів шлях тоді й лише тоді, коли найдовший шлях у ньому має довжину n − 1, де n — число вершин графа G. Оскільки задача пошуку гамільтонового шляху є NP-повною, це зведення показує, що задача пошуку найдовшого шляху у варіанті розв'язності також NP-повна. У цій задачі розв'язності входом є граф G і число k. Очікується вихід «так», якщо G містить шлях з k і більше дугами, або ні в іншому разі.

Якби задачу пошуку найдовшого шляху можна було розв'язати за поліноміальний час, її можна було б використати для розв'язання цієї задачі розв'язності, знайшовши найдовший шлях та порівнявши його довжину з числом k. Таким чином, задача пошуку найдовшого шляху є NP-складною. Вона не є NP-повною, оскільки вона не є задачею розв'язності.

У зважених повних графах із невід'ємними вагами ребер задача пошуку зваженого найдовшого шляху є тією ж задачею, що й задача комівояжера, оскільки найдовший шлях завжди включає всі вершини цієї задачі.

Ациклічні графи та критичні шляхи

Найдовший шлях A між двома заданими вершинами s і t у зваженому графі G — це те саме, що й найкоротший шлях у графі −G, отриманому з G заміною всіх ваг на ваги з протилежним знаком. Отже, якщо можна знайти найкоротший шлях в −G, то можна знайти і найдовший шлях у G.

Для більшості графів таке перетворення марне, оскільки створює в −G цикли від'ємної довжини. Але якщо G є спрямованим ациклічним графом, від'ємний цикл створити неможливо і найдовший шлях у G можна знайти за лінійний час, застосувавши алгоритм пошуку найкоротшого шляху в −G (теж орієнтованому ациклічному графі), який працює за лінійний час . Наприклад, для будь-якої вершини v в орієнтованому ациклічному графі довжину найдовшого шляху, що закінчується у v, можна отримати, виконавши такі кроки: Коли це буде зроблено, найдовший шлях у всьому графі можна отримати, почавши з вершини v з найбільшим записаним значенням і проходячи у зворотному порядку, вибираючи вхідну дугу, в якої запис у початковій вершині має найбільше значення.

Метод критичного шляху для планування набору робіт використовує побудову орієнтованого ациклічного графа, в якому вершини представляють вузлові події проекту, а дуги представляють роботи, які мають бути виконані до вузлової події і після неї. Кожній дузі присвоюється вага, що дорівнює оцінці часу виконання роботи. У такому графі найдовший шлях від першої вузлової події до останньої є критичним шляхом, який визначає повний час завершення проєкту.

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

Наближення

Бьорклунд, Гасфелдт і Канна писали, що задача пошуку найдовшого шляху в незваженому неорієнтованому графі є «сумно відомою за складністю розуміння труднощів її апроксимації». Найкращий відомий алгоритм апроксимації поліноміального часу виконання дає лише дуже слабку апроксимацію, $n/\exp(\Omega ({\sqrt {\log n}}))$. Для будь-якого $\epsilon >0$ неможливо апроксимувати найдовший шлях із множником, меншим від $2^{(\log n)^{1-\epsilon }}$, якщо тільки NP не належить до задач квазіполіноміального детермінованого часу. Однак існує великий розрив між цим результатом апроксимованості та відомими алгоритмами апроксимації для цієї задачі.

У разі незважених, але орієнтованих графів відомі сильні результати апроксимованості. Для будь-якого $\epsilon >0$ задачу не можна апроксимувати в межах $n^{1-\epsilon }$, якщо тільки не P = NP, і, за сильних теоретичних припущень, задачу не можна апроксимувати в межах $n/\log ^{2+\epsilon }n$. Для пошуку шляху логарифмічної довжини, якщо він існує, можна використати техніку колірного кодування, але вона дає апроксимаційний коефіцієнт лише $O(n/\log n)$.

Параметризована складність

Задача пошуку найдовшого шляху є фіксовано-параметрично розв'язною, якщо параметризувати її за довжиною шляху. Наприклад, задачу можна розв'язати за час, що лінійно залежить від розміру вхідного графа (але за експоненційний час за довжиною шляху), за допомогою алгоритму, що включає такі кроки:

1. Здійснюємо пошук у глибину за графом. Нехай $d$ — глибина кінцевого дерева пошуку вглиб.
2. Використовуємо шляхи від кореня до листів пошуку дерева вглиб у порядку, в якому вони переглядаються під час пошуку, на відміну від шляхової декомпозиції графа зі шляховою шириною $d$ .
3. Використовуємо динамічне програмування до цього розкладу на шляхи для знаходження найдовшого шляху за час $O(d!2^{d}n)$, де $n$ — число вершин графа.

Оскільки початковий шлях має довжину щонайменше $d$, час роботи також буде обмежено значенням $O(\ell !2^{\ell }n)$, де $\ell$ — довжина найдовшого шляху. Використовуючи колірне кодування, залежність від довжини шляху можна звести до одинично експоненційної. Схожа техніка динамічного програмування показує, що задача пошуку найдовшого шляху є також фіксовано-параметрично розв'язною за деревною шириною графа.

Для графів з обмеженою кліковою шириною задачу про найдовший шлях можна розв'язати за поліноміальний час за допомогою алгоритму динамічного програмування. Однак степінь полінома залежить від клікової ширини графа, тому ці алгоритми не є фіксовано-параметрично розв'язними. Задача знаходження найдовшого шляху, параметризована за кліковою шириною, є складною для класу парметризованої складності $W[1]$, що говорить про те, що навряд чи існує фіксовано-параметрично розв'язний алгоритм.

Особливі випадки графів

Задача про найдовший шлях можна розв'язати за поліноміальний час на доповненнях графів порівнянності. Також її можна розв'язати за поліноміальний час на будь-якому класі графів із обмеженою деревною шириною або обмеженою кліковою шириною, такому як дистанційно-успадковувані графи. Однак задача є NP-складною, навіть якщо обмежитися розщеплюваними графами, коловими графами або планарними графами.

Див. також

• Теорема Галлаї — Гассе — Роя — Вітавера, двоїстість найдовшого шляху та розфарбування графів
• Задача про хід коня
• Задача про змію в коробці, найдовший породжений шлях у графі гіперкуба

Література

• 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. — arXiv:0807.3026. — DOI:10.1016/j.ipl.2008.11.004.
• 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)