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

Задача нахождения самого длинного простого пути для заданного графа

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

NP-твердость

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

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

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

Ациклические графы

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

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

Аналогично, для каждой вершины v в данном DAG длина самого длинного пути, заканчивающегося в v, может быть получена с помощью следующих шагов:

1. Найдите топологическое упорядочение данного DAG.
2. Для каждой вершины v DAG в топологическом порядке вычислите длину самого длинного пути, заканчивающегося в v , просматривая его входящих соседей и добавляя единицу к максимальной длине, записанной для этих соседей. Если у v нет входящих соседей, установите длину самого длинного пути, заканчивающегося в v, на ноль. В любом случае запишите это число, чтобы последующие шаги алгоритма могли получить к нему доступ.

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

Это эквивалентно запуску алгоритма кратчайшего пути на −G .

Критические пути

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

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

Приближение

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

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

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

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

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

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

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

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

Алгоритм линейного времени для поиска самого длинного пути в дереве был предложен Эдсгером Дейкстрой около 1960 года, а формальное доказательство этого алгоритма было опубликовано в 2002 году. ^[15] Кроме того, самый длинный путь может быть вычислен за полиномиальное время на взвешенных деревьях, на блочных графах , на кактусах , ^[16] на двудольных графах перестановок , ^[17] и на птолемеевых графах . ^[18]

Для класса интервальных графов известен алгоритм с -временем, который использует подход динамического программирования. [ ^19] Этот подход динамического программирования был использован для получения алгоритмов с полиномиальным временем выполнения на больших классах графов с дугами окружности ^[20] и графов совместной сравнимости (т. е. дополнений графов сравнимости , которые также содержат графы перестановок ), ^[21] оба имеют одинаковое время выполнения . Последний алгоритм основан на специальных свойствах упорядочения вершин лексикографического поиска в глубину (LDFS) ^[22] графов совместной сравнимости. Для графов совместной сравнимости также известен альтернативный алгоритм с полиномиальным временем выполнения с более высоким временем выполнения, который основан на диаграмме Хассе частично упорядоченного множества, определяемого дополнением входного графа совместной сравнимости. ^[23] ${\displaystyle O(n^{4})}$ ${\displaystyle O(n^{4})}$ ${\displaystyle O(n^{7})}$

Более того, задача о самом длинном пути разрешима за полиномиальное время на любом классе графов с ограниченной древовидной шириной или ограниченной кликовой шириной, например, на дистанционно-наследуемых графах . Наконец, она, очевидно, NP-трудна на всех классах графов, на которых задача о гамильтоновом пути является NP-трудной, например, на расщепленных графах , круговых графах и планарных графах .

Простая модель направленного ациклического графа — это модель Прайса , разработанная Дереком Дж. де Соллой Прайсом для представления сетей цитирования . Она достаточно проста, чтобы позволить находить аналитические результаты для некоторых свойств. Например, длина самого длинного пути от n-го узла, добавленного в сеть, до первого узла в сети масштабируется как ^[24] . ${\displaystyle \ln(n)}$

Смотрите также

• Теорема Галлаи–Хассе–Роя–Витавера , соотношение двойственности между длиннейшими путями и раскраской графа
• Самый длинный непересекаемый путь рыцаря
• Змея в коробке , самый длинный индуцированный путь в графе гиперкуба
• Модель Прайса , простая модель сети цитирования, в которой самые длинные пути можно найти аналитически.

Ссылки

1. Schrijver, Alexander (2003), Комбинаторная оптимизация: многогранники и эффективность, том 1, Алгоритмы и комбинаторика, т. 24, Springer, стр. 114, ISBN 9783540443896.
2. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001), Введение в алгоритмы (2-е изд.), MIT Press, стр. 978, ISBN 9780262032933.
3. Лоулер, Юджин Л. (2001), Комбинаторная оптимизация: сети и матроиды, Courier Dover Publications, стр. 64, ISBN 9780486414539.
4. Седжвик, Роберт ; Уэйн, Кевин Дэниел (2011), Алгоритмы (4-е изд.), Addison-Wesley Professional, стр. 661–666, ISBN 9780321573513.
5. Ди Баттиста, Джузеппе; Идс, Питер ; Тамассиа, Роберто ; Толлис, Иоаннис Г. (1998), «Слоистые рисунки орграфов», Рисование графов: алгоритмы визуализации графов , Prentice Hall , стр. 265–302, ISBN 978-0-13-301615-4.
6. Björklund, Andreas; Husfeldt, Thore; Khanna, Sanjeev (2004), "Аппроксимация самых длинных направленных путей и циклов", Proc. Int. Coll. Automata, Languages ​​and Programming (ICALP 2004) , Lecture Notes in Computer Science , т. 3142, Berlin: Springer-Verlag, стр. 222–233, MR  2160935.
7. Габов, Гарольд Н.; Ни, Шуксин (2008), «Поиск длинных путей, циклов и цепей», Международный симпозиум по алгоритмам и вычислениям , Lecture Notes in Computer Science, т. 5369, Берлин: Springer, стр. 752–763, doi :10.1007/978-3-540-92182-0_66, ISBN 978-3-540-92181-3, г-н  2539968. Для более ранней работы с еще более слабыми границами приближения см. Gabow, Harold N. (2007), "Finding paths and cycles of superpolylogarithmic length" (PDF) , SIAM Journal on Computing , 36 (6): 1648–1671, doi :10.1137/S0097539704445366, MR  2299418и Бьёрклунд, Андреас; Хусфельдт, Тор (2003), «Поиск пути суперлогарифмической длины», SIAM Journal on Computing , 32 (6): 1395–1402, doi :10.1137/S0097539702416761, MR  2034242.
8. Каргер, Дэвид ; Мотвани, Раджив ; Рамкумар, GDS (1997), «Об аппроксимации самого длинного пути в графе», Algorithmica , 18 (1): 82–98, doi :10.1007/BF02523689, MR  1432030, S2CID  3241830.
9. Alon, Noga ; Yuster, Raphael; Zwick, Uri (1995), «Цветовое кодирование», Journal of the ACM , 42 (4): 844–856, doi : 10.1145/210332.210337 , MR  1411787, S2CID  208936467.
10. Бодлендер, Ханс Л. (1993), «О линейных второстепенных тестах с поиском в глубину», Журнал алгоритмов , 14 (1): 1–23, doi :10.1006/jagm.1993.1001, MR  1199244. Для более раннего алгоритма FPT с немного лучшей зависимостью от длины пути, но худшей зависимостью от размера графа, см. Monien, B. (1985), "Как эффективно находить длинные пути", Анализ и проектирование алгоритмов для комбинаторных задач (Удине, 1982), North-Holland Math. Stud., т. 109, Амстердам: North-Holland, стр. 239–254, doi :10.1016/S0304-0208(08)73110-4, ISBN 9780444876997, МР  0808004.
11. Чэнь, Цзяньэр; Лу, Сунцзянь; Сзе, Синг-Хой; Чжан, Фэнхуэй (2007), «Улучшенные алгоритмы для задач поиска путей, сопоставления и упаковки», Труды 18-го симпозиума ACM-SIAM по дискретным алгоритмам (SODA '07) (PDF) , стр. 298–307.
12. Коутис, Иоаннис (2008), «Быстрые алгебраические алгоритмы для задач поиска путей и упаковки», Международный коллоквиум по автоматам, языкам и программированию (PDF) , Lecture Notes in Computer Science, т. 5125, Берлин: Springer, стр. 575–586, CiteSeerX 10.1.1.141.6899 , doi :10.1007/978-3-540-70575-8_47, ISBN  978-3-540-70574-1, MR  2500302, архивировано из оригинала (PDF) 2017-08-09 , извлечено 2013-08-09.
13. Уильямс, Райан (2009), «Нахождение путей длины k за время O *(2 ^k )», Information Processing Letters , 109 (6): 315–318, arXiv : 0807.3026 , doi : 10.1016/j.ipl.2008.11.004, MR  2493730, S2CID  10295448.
14. Фомин, Федор В.; Головач, Петр А.; Локштанов, Даниэль; Саурабх, Сакет (2009), «Ширина клики: цена общности», Proc. 20th ACM-SIAM Symposium on Discrete Algorithms (SODA '09) (PDF) , стр. 825–834, архивировано из оригинала (PDF) 2012-10-18 , извлечено 2012-12-01.
15. Балтерман, RW; ван дер Соммен, ФРВ; Зваан, Г.; Верховев, Т.; ван Гастерен, AJM (2002), «О вычислении самого длинного пути в дереве», Information Processing Letters , 81 (2): 93–96, doi : 10.1016/S0020-0190(01)00198-3.
16. Uehara, Ryuhei; Uno, Yushi (2004), "Эффективные алгоритмы для задачи о самом длинном пути", в Fleischer, Rudolf; Trippen, Gerhard (ред.), Algorithms and Computation, 15th International Symposium, ISAAC 2004, Hong Kong, China, 20-22 декабря 2004 г., Proceedings , Lecture Notes in Computer Science, т. 3341, Springer, стр. 871–883, doi :10.1007/978-3-540-30551-4_74, ISBN 978-3-540-24131-7.
17. Уэхара, Рюхэй; Валиенте, Габриэль (2007), «Линейная структура двудольных графов перестановок и проблема самого длинного пути», Information Processing Letters , 103 (2): 71–77, CiteSeerX 10.1.1.101.96 , doi :10.1016/j.ipl.2007.02.010 .
18. Такахара, Ёсихиро; Терамото, Сачио; Уэхара, Рюхэй (2008), «Проблемы с самым длинным путем на птолемеевых графах», IEICE Transactions , 91-D (2): 170–177, doi : 10.1093/ietisy/e91-d.2.170.
19. Иоанниду, Кириаки; Мерциос, Джордж Б.; Николопулос, Ставрос Д. (2011), «Задача о наибольшем пути имеет полиномиальное решение на интервальных графах», Algorithmica , 61 (2): 320–341, CiteSeerX 10.1.1.224.4927 , doi : 10.1007/s00453-010-9411 -3, S2CID  7577817 .
20. Мерциос, Джордж Б.; Безакова, Ивона (2014), «Вычисление и подсчет длиннейших путей на графах с дугами окружности за полиномиальное время», Дискретная прикладная математика , 164 (2): 383–399, CiteSeerX 10.1.1.224.779 , doi :10.1016/j.dam.2012.08.024 .
21. Мерциос, Джордж Б.; Корнейл, Дерек Г. (2012), «Простой полиномиальный алгоритм для задачи поиска самого длинного пути на графах сопоставимости», SIAM Journal on Discrete Mathematics , 26 (3): 940–963, arXiv : 1004.4560 , doi : 10.1137/100793529, S2CID  4645245.
22. Корнейл, Дерек Г.; Крюгер, Ричард (2008), «Единый взгляд на поиск графов», SIAM Journal on Discrete Mathematics , 22 (4): 1259–1276, doi :10.1137/050623498.
23. Иоанниду, Кириаки; Николопулос, Ставрос Д. (2011), «Задача о наибольшем пути является полиномиальной на графах сосравнимости» (PDF) , Algorithmica , 65 : 177–205, CiteSeerX 10.1.1.415.9996 , doi :10.1007/s00453-011-9583-5 , S2CID  7271040 .
24. Эванс, ТС; Калмон, Л.; Василяускайте, В. (2020), «Самый длинный путь в модели цен», Scientific Reports , 10 (1): 10503, arXiv : 1903.03667 , Bibcode : 2020NatSR..1010503E, doi : 10.1038/s41598-020-67421-8, PMC 7324613 , PMID  32601403 

Внешние ссылки

• «Find the Longest Path», песня Дэна Барретта