Задача о самом длинном пути — это задача поиска простого пути максимальной длины в заданном графе. Путь называется простым, если в нём нет повторных вершин. Длина пути может быть измерена либо числом рёбер, либо (в случае взвешенных графов) суммой весов его рёбер. В отличие от задачи кратчайшего пути, которая может быть решена за полиномиальное время на графах без циклов с отрицательным весом, задача нахождения самого длинного пути является 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, может быть получена выполнением следующих шагов: Осуществляем топологическую сортировку заданного ориентированного ациклического графа (ОАГ). Для каждой вершины v ОАГ в топологической сортировке вычисляем длину самого длинного пути, завершающегося в вершине v путём просмотра входящих дуг от соседей и добавления единички к максимальной длине в записях этих соседей. Если v не имеет входящих дуг, присваиваем длину самого длинного пути, кончающегося в v, нулю. Когда это будет сделано, самый длинный путь во всём графе можно получить, начав с вершины v с самым большим записанным значением и проходя в обратном порядке, выбирая входящую дугу, у которой запись в начальной вершине имеет наибольшее значение.

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

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

Приближение Бьёрклунд, Хасфелдт и Канна писали, что задача поиска самого длинного пути в невзвешенном неориентированном графе является «печально известной по сложности понимания её трудности аппроксимации». Лучший известный алгоритм аппроксимации полиномиального времени выполнения даёт лишь очень слабую аппроксимацию, . Для более ранних работ даже с более слабой аппроксимацией см. статьи Габова и Бьёрклунда и Хасфелдта .. Для любого невозможно аппроксимировать самый длинный путь со множителем, меньшим , если только NP не принадлежит задачам квазиполиномиального детерминированного времени. Однако существует большой разрыв между этим результатом аппроксимируемости и известными алгоритмами аппроксимации для этой задачи.

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

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

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

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

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

Примечания

Литература

Метод нечёткого критического пути / Акимов В. А., Балашов В. Г., Заложнев А. Ю. // Управление большими системами. Выпуск 3. М.: ИПУ РАН, 2003. С. 5-10.

Ссылки "Find the Longest Path", песня Дана Барретта (Dan Barrett)

Категория:NP-полные задачи Категория:Алгоритмы на графах Категория:Вычислительные задачи теории графов Категория:Гамильтоновы пути и циклы