Проблема самого длинного пути - Longest path problem

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

NP-твердость

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

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

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

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

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

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

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

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

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

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

Приближение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рекомендации

1. Шрайвер, Александр (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. Бьёрклунд, Андреас; Хусфельдт, Тор; Кханна, Санджив (2004), «Приближение самых длинных направленных путей и циклов», Proc. Int. Coll. Автоматы, языки и программирование (ICALP 2004), Конспект лекций по информатике, 3142, Берлин: Springer-Verlag, стр. 222–233, МИСТЕР  2160935.
7. Габоу, Гарольд Н .; Не, Шуксин (2008), «Поиск длинных путей, циклов и схем», Международный симпозиум по алгоритмам и вычислениям, Конспект лекций по информатике, 5369, Берлин: Springer, стр. 752–763, Дои:10.1007/978-3-540-92182-0_66, ISBN  978-3-540-92181-3, МИСТЕР  2539968. Более ранние работы с еще более слабыми оценками приближения см. Габоу, Гарольд Н. (2007), «Поиск путей и циклов суперполилогарифмической длины» (PDF), SIAM Журнал по вычислениям, 36 (6): 1648–1671, Дои:10.1137 / S0097539704445366, МИСТЕР  2299418 и Бьёрклунд, Андреас; Хусфельдт, Тор (2003), «Нахождение пути суперлогарифмической длины», SIAM Журнал по вычислениям, 32 (6): 1395–1402, Дои:10.1137 / S0097539702416761, МИСТЕР  2034242.
8. Каргер, Дэвид; Мотвани, Раджив; Рамкумар, Г. Д. С. (1997), "Об аппроксимации самого длинного пути в графе", Алгоритмика, 18 (1): 82–98, Дои:10.1007 / BF02523689, МИСТЕР  1432030, S2CID  3241830.
9. Алон, Нога; Юстер, Рафаэль; Цвик, Ури (1995), «Цветовая кодировка», Журнал ACM, 42 (4): 844–856, Дои:10.1145/210332.210337, МИСТЕР  1411787, S2CID  208936467.
10. Бодландер, Ханс Л. (1993), "О малых тестах линейного времени с поиском в глубину", Журнал алгоритмов, 14 (1): 1–23, Дои:10.1006 / jagm.1993.1001, МИСТЕР  1199244. Для более раннего алгоритма FPT с немного лучшей зависимостью от длины пути, но худшей зависимостью от размера графа, см. Моньен, Б. (1985), "Как эффективно находить длинные пути", Анализ и разработка алгоритмов комбинаторных задач (Удине, 1982), Северная Голландия Math. Stud., 109, Амстердам: Северная Голландия, стр. 239–254, Дои:10.1016 / S0304-0208 (08) 73110-4, ISBN  9780444876997, МИСТЕР  0808004.
11. Чен, Цзианэр; Лу, Сунцзянь; Сзе, Синг-Хой; Чжан, Фэнхуэй (2007), «Улучшенные алгоритмы для задач пути, сопоставления и упаковки», Proc. 18-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA '07) (PDF), стр. 298–307.
12. Кутис, Иоаннис (2008 г.), «Более быстрые алгебраические алгоритмы для проблем с путями и упаковкой», Международный коллоквиум по автоматам, языкам и программированию (PDF), Конспект лекций по информатике, 5125, Берлин: Springer, стр. 575–586, CiteSeerX  10.1.1.141.6899, Дои:10.1007/978-3-540-70575-8_47, ISBN  978-3-540-70574-1, МИСТЕР  2500302, заархивировано из оригинал (PDF) на 2017-08-09, получено 2013-08-09.
13. Уильямс, Райан (2009), «Поиск путей длины k в О*(2^k) время", Письма об обработке информации, 109 (6): 315–318, arXiv:0807.3026, Дои:10.1016 / j.ipl.2008.11.004, МИСТЕР  2493730, S2CID  10295448.
14. Фомин, Федор В .; Головач, Петр А .; Локштанов Даниил; Саураб, Сакет (2009), «Ширина клики: по цене общности», Proc. 20-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA '09) (PDF), pp. 825–834, архивировано с оригинал (PDF) на 2012-10-18, получено 2012-12-01.
15. Bulterman, R.W .; van der Sommen, F.W .; Zwaan, G .; Verhoeff, T .; ван Гастерен, А.Дж.М. (2002), «О вычислении самого длинного пути в дереве», Письма об обработке информации, 81 (2): 93–96, Дои:10.1016 / S0020-0190 (01) 00198-3.
16. Уэхара, Рюхей; Уно, Юши (2004 г.), "Эффективные алгоритмы для решения задачи наибольшей длины пути", Исаак 2004, Конспект лекций по информатике, 3341: 871–883, Дои:10.1007/978-3-540-30551-4_74, ISBN  978-3-540-24131-7.
17. Уэхара, Рюхей; Валиенте, Габриэль (2007), "Линейная структура двудольных графов перестановок и проблема самого длинного пути", Письма об обработке информации, 103 (2): 71–77, CiteSeerX  10.1.1.101.96, Дои:10.1016 / j.ipl.2007.02.010.
18. Такахара, Йошихиро; Терамото, Сачио; Уэхара, Рюхей (2008), "Задачи о самом длинном пути на птолемеевых графах", IEICE транзакции, 91-D (2): 170–177, Дои:10.1093 / ietisy / e91-d.2.170.
19. Иоанниду, Кириаки; Мерциос, Джордж Б .; Николопулос, Ставрос Д. (2011), "Задача о самом длинном пути имеет полиномиальное решение на интервальных графах", Алгоритмика, 61 (2): 320–341, CiteSeerX  10.1.1.224.4927, Дои:10.1007 / s00453-010-9411-3, S2CID  7577817.
20. Мерциос, Джордж Б .; Безакова, Ивона (2014), "Вычисление и подсчет самых длинных путей на круговых графах за полиномиальное время", Дискретная прикладная математика, 164 (2): 383–399, CiteSeerX  10.1.1.224.779, Дои:10.1016 / j.dam.2012.08.024.
21. Мерциос, Джордж Б .; Корнейл, Дерек Г. (2012), "Простой полиномиальный алгоритм для задачи о самом длинном пути на графах кокосопарабельности", Журнал SIAM по дискретной математике, 26 (3): 940–963, arXiv:1004.4560, Дои:10.1137/100793529, S2CID  4645245.
22. Корнейл, Дерек Дж .; Крюгер, Ричард (2008), «Единый взгляд на поиск в графах», Журнал SIAM по дискретной математике, 22 (4): 1259–1276, Дои:10.1137/050623498.
23. Иоанниду, Кириаки; Николопулос, Ставрос Д. (2011), «Задача о самом длинном пути полиномиальна на графах кокосовместимости» (PDF), Алгоритмика, 65: 177–205, CiteSeerX  10.1.1.415.9996, Дои:10.1007 / s00453-011-9583-5, S2CID  7271040.
24. Evans, T.S .; Calmon, L .; Василяускайте, В. (2020), «Самый длинный путь в ценовой модели», Научные отчеты, 10 (1): 10503, arXiv:1903.03667, Bibcode:2020НатСР..1010503Е, Дои:10.1038 / s41598-020-67421-8, ЧВК  7324613, PMID  32601403

внешняя ссылка

• "Найдите самый длинный путь ", песня Дэн Барретт