WikiDer > Проблема самого длинного пути

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  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. ^ а б c Седжвик, Роберт; Уэйн, Кевин Дэниел (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 в О*(2k) время", Письма об обработке информации, 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

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