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

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

NP-твердость

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

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

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

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

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

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

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

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

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

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

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

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

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

Приближение

Бьорклунд, Хусфельдт и Ханна (2004) пишут, что задача о самом длинном пути в невзвешенных неориентированных графах «печально известна трудностью понимания сложности ее аппроксимации». Лучший алгоритм аппроксимации с полиномиальным временем, известный для этого случая, обеспечивает лишь очень слабую степень аппроксимации: $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]$, показывая, что управляемый алгоритм с фиксированными параметрами вряд ли существует.

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

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

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

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

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

См. также

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

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

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