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

NP-трудность

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

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

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

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

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

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

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

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

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

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

Приближение

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

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

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

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

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

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

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

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

См. также

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

Примечания

Литература

Ссылки

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