Из Википедии, бесплатной энциклопедии
  (Перенаправлен с самого длинного пути )
Перейти к навигации Перейти к поиску

В теории графов и теоретической информатике самой длинной проблемой пути является проблема поиска простого пути максимальной длины в заданном графе. Путь называется простым, если он не имеет повторяющихся вершин; длина пути может быть измерена либо числом его ребер, либо (в взвешенных графах ) суммой весов его ребер. В отличие от задачи о кратчайшем пути , которая может быть решена за полиномиальное время в графах без циклов с отрицательным весом, задача о самом длинном пути является 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 - ориентированный ациклический граф , то отрицательные циклы не могут быть созданы, и самый длинный путь в G может быть найден за линейное время , применяя алгоритм линейного времени для кратчайших путей в -G , который также является ориентированным ациклическим графом. [4] Например, для каждой вершины v в данном DAG длина самого длинного пути, заканчивающегося в v, может быть получена с помощью следующих шагов:

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

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

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

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

Приближение [ править ]

Björklund, Husfeldt & Khanna (2004) пишут, что проблема самого длинного пути в невзвешенных неориентированных графах «печально известна трудностью понимания сложности ее аппроксимации». [6] Лучший полином время алгоритм аппроксимации известен для этого случая достигает лишь очень слабое отношение аппроксимации, . [7] Для всех,невозможно аппроксимировать самый длинный путь с точностью до множителя, если NP не содержится в квазиполиномиальном детерминированном времени ; однако существует большой разрыв между этим результатом о недопустимости приближения и известными алгоритмами аппроксимации для этой проблемы. [8]

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

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

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

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

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

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

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

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

Для класса графов интервалов , -time алгоритм известен, который использует динамическое программный подход. [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. ^ a b c Седжвик, Роберт ; Уэйн, Кевин Дэниел (2011), Алгоритмы (4-е изд.), Addison-Wesley Professional, стр. 661–666, ISBN 9780321573513.
  5. ^ Ди Баттиста, Джузеппе; Идс, Питер ; Тамассия, Роберто ; Толлис, Иоаннис Г. (1998), «Многослойные рисунки орграфов», Graph Drawing: Algorithms for the Visualization of Graph , Prentice Hall , pp. 265–302, ISBN 978-0-13-301615-4.
  6. ^ a b Бьёрклунд, Андреас; Хусфельдт, Тор; Кханна, Санджив (2004), «Аппроксимация самых длинных направленных путей и циклов», Proc. Int. Coll. Автоматы, языки и программирование (ICALP 2004) , Lecture Notes in Computer Science , 3142 , Berlin: Springer-Verlag, pp. 222–233, MR 2160935. .
  7. ^ Габоу, Гарольд Н .; Ни, Шуксин (2008), «Поиск длинных путей, циклов и схем», Международный симпозиум по алгоритмам и вычислениям , конспект лекций по информатике, 5369 , Берлин: Springer, стр. 752–763, doi : 10.1007 / 978-3- 540-92182-0_66 , ISBN 978-3-540-92181-3, Руководство по ремонту  2539968. Для более ранней работы с еще более слабыми границами приближения см. Габоу, Гарольд Н. (2007), «Поиск путей и циклов суперполилогарифмической длины» (PDF) , SIAM Journal on Computing , 36 (6): 1648–1671, doi : 10.1137 / S0097539704445366 , МР 2299418  и Бьёрклунд, Андреас; Husfeldt, Thore (2003), "Нахождение пути superlogarithmic длины" , SIAM журнал по вычислениям , 32 (6): 1395-1402, DOI : 10,1137 / S0097539702416761 , МР 2034242 .
  8. ^ Каргер, Дэвид ; Мотвани, Раджив ; Рамкумар, ГРС (1997), "О приближении самого длинного пути в графе", Algorithmica , 18 (1): 82-98, DOI : 10.1007 / BF02523689 , МР 1432030 , S2CID 3241830  .
  9. ^ а б Алон, Нога ; Юстер, Рафаэль; Цвик, Ури (1995), "Цвет-кодирование", Журнал ACM , 42 (4): 844-856, DOI : 10,1145 / 210332,210337 , МР 1411787 , S2CID 208936467  .
  10. ^ Bodlaender, Ганс Л. (1993), "О линейных время испытаний с незначительными поиска в глубину", журнал алгоритмов , 14 (1): 1-23, DOI : 10,1006 / jagm.1993.1001 , МР 1199244 . Для более раннего алгоритма FPT с немного лучшей зависимостью от длины пути, но худшей зависимостью от размера графа, см. Monien, B. (1985), «Как эффективно находить длинные пути», Анализ и разработка алгоритмов для комбинаторных задач. (Удине, 1982) , North Holland Math. Stud,. 109 , Амстердам.: Северная Голландия, С. 239-254, DOI : 10.1016 / S0304-0208 (08) 73110-4 , ISBN 9780444876997, Руководство по ремонту  0808004.
  11. ^ Chen, Jianer; Лу, Сунцзянь; Сзе, Синг-Хой; Zhang, Fenghui (2007), «Улучшенные алгоритмы для задач пути, сопоставления и упаковки», Proc. 18-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA '07) (PDF) , стр. 298–307 .
  12. ^ Koutis, Иоаннис (2008), "Быстрее алгебраические алгоритмы для пути и упаковки задач", Международный коллоквиум автоматного, языки и программирование (PDF) , Lecture Notes в области компьютерных наук, 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) 09.08.2017 , получено 09.08.2013.
  13. ^ Уильямс, Райан (2009), «Поиск путей длины k за время O * (2 k )», Письма об обработке информации , 109 (6): 315–318, arXiv : 0807.3026 , doi : 10.1016 / j.ipl.2008.11 .004 , Руководство по ремонту 2493730 , S2CID 10295448  .
  14. ^ Фомин, Федор В .; Головач, Петр А .; Локштанов Даниил; Саураб, Сакет (2009), «Ширина клики: по цене общности», Proc. Двадцатый ACM-SIAM симпозиум по дискретным алгоритмам (SODA '09) (PDF) , стр. 825-834, архивируется с оригинала (PDF) на 2012-10-18 , извлекается 2012-12-01 .
  15. ^ Бултерман, RW; ван дер Соммен, ФВ; Zwaan, G .; Verhoeff, T .; ван Гастерен, AJM (2002), «О вычислении самого длинного пути в дереве», Письма об обработке информации , 81 (2): 93–96, DOI : 10.1016 / S0020-0190 (01) 00198-3.
  16. ^ Уэхара, Рюхей; Uno, Yushi (2004), "Эффективные алгоритмы для самого длинного пути проблемы", Isaac 2004 , Lecture Notes в области компьютерных наук, 3341 : 871-883, DOI : 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 , doi : 10.1016 / j.ipl.2007.02 0,010 .
  18. ^ ТАКАХАРА, Yoshihiro; Терамото, Сачио; Уэхара, Рюхэй (2008), "Самый длинный путь на проблемы Птолемеев графов", IEICE сделок , 91-D (2): 170-177, дой : 10,1093 / ietisy / E91-d.2.170.
  19. ^ Иоаннида, Kyriaki; Мерциос, Джордж Б .; Nikolopoulos, Ставрос D. (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. ^ Корнейл, Дерек G .; Krueger, Ричард (2008), "Единый вид поиска графа", SIAM журнал по дискретной математике , 22 (4): 1259-1276, DOI : 10,1137 / 050623498.
  23. ^ Иоаннида, Kyriaki; Nikolopoulos, Ставрос D. (2011), "Самый длинный путь проблема является полиномом на cocomparability графах" (PDF) , Algorithmica , 65 : 177-205, CiteSeerX 10.1.1.415.9996 , DOI : 10.1007 / s00453-011-9583-5 , S2CID 7271040   .
  24. ^ Evans, TS; Calmon, L .; Василяускайте, В. (2020), «Самый длинный путь в ценовой модели», Научные отчеты , 10 (1): 10503, arXiv : 1903.03667 , Bibcode : 2020NatSR..1010503E , doi : 10.1038 / s41598-020-67421-8 , PMC 7324613 , PMID 32601403  

Внешние ссылки [ править ]

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