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

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

NP-трудность

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

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

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

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

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

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

1. Осуществляем топологическую сортировку заданного ориентированного ациклического графа (ОАГ).
2. Для каждой вершины v ОАГ в топологической сортировке вычисляем длину самого длинного пути, завершающегося в вершине v путём просмотра входящих дуг от соседей и добавления единички к максимальной длине в записях этих соседей. Если v не имеет входящих дуг, присваиваем длину самого длинного пути, кончающегося в v, нулю.

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

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

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

Приближение

Бьёрклунд, Хасфелдт и Канна писали, что задача поиска самого длинного пути в невзвешенном неориентированном графе является «печально известной по сложности понимания её трудности аппроксимации»^[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]. Можно использовать технику цветовой кодировки^[en] для поиска пути логарифмической длины, если он существует, но эта техника даёт аппроксимационный коэффициент лишь ${\displaystyle O(n/\log n)}$^[9].

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

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

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]. Используя цветовую кодировку, зависимость от длины пути может быть сведена к одиночно экспоненциальной^[11][12][13]. Похожая техника динамического программирования показывает, что задача нахождения самого длинного пути является также фиксированно-параметрически разрешимой по древесной ширине графа.

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

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

Задачу о самом длинном пути можно решить за полиномиальное время на дополнениях графов сравнимости^[15]. Её можно решить также за полиномиальное время на любом классе графов с ограниченной древесной шириной или ограниченной кликовой шириной, таком как дистанционно-наследуемые графы. Однако задача является NP-трудной, даже если ограничимся расщепляемыми графами, круговыми графами или планарными графами^[16].

См. также

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

Примечания

Литература

Ссылки

• "Find the Longest Path", песня Дана Барретта (Dan Barrett)

Эта страница в последний раз была отредактирована 5 ноября 2022 в 17:28.