4511
правок
Вершинное покрытие и деревья поиска: различия между версиями
Материал из WEGA
Вершинное покрытие и деревья поиска (посмотреть исходный код)
Версия от 00:29, 16 июля 2016
, 16 июля 2016нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 20: | Строка 20: | ||
Предположим, что (G, k) – экземпляр задачи о вершинном покрытии, где G – граф, а k – параметр. Операция кернелизации применяет к экземпляру (G, k) подпрограмму обработки с полиномиальным временем выполнения, которая строит еще один экземпляр (G’, k’), где G’ – граф меньшего размера (ядро), а <math>k’ \le k \;</math>, такой, что G’ имеет вершинное покрытие из k’ вершин в том и только том случае, если G имеет вершинное покрытие из k вершин. В классической работе Немхаузера и Троттера [9] был получен следующий результат, относящийся к кернелизации. | Предположим, что (G, k) – экземпляр задачи о вершинном покрытии, где G – граф, а k – параметр. Операция кернелизации применяет к экземпляру (G, k) подпрограмму обработки с полиномиальным временем выполнения, которая строит еще один экземпляр (G’, k’), где G’ – граф меньшего размера (ядро), а <math>k’ \le k \;</math>, такой, что G’ имеет вершинное покрытие из k’ вершин в том и только том случае, если G имеет вершинное покрытие из k вершин. В классической работе Немхаузера и Троттера [9] был получен следующий результат, относящийся к кернелизации. | ||
''' | |||
Теорема 1. Существует алгоритм решения задачи о вершинном покрытии с временем выполнения <math>O(kn + k^3) \;</math>, который для экземпляра (G, k) строит еще один экземпляр задачи (G’, k’), где граф G’ содержит не более 2k’ вершин, а <math>k’ \le k \;</math>, такой, что граф G имеет вершинное покрытие из k вершин в том и только том случае, если граф G’ имеет вершинное покрытие из k’ вершин.''' | |||
Таким образом, кернелизация обеспечивает эффективную предварительную подготовку для решения задачи о вершинном покрытии, которая позволяет работать с графами меньшего размера (т.е. с графами, размер которых зависит только от k). | |||
== Свертка == | == Свертка == | ||
| Строка 30: | Строка 31: | ||
Теорема 2. Пусть G’ – граф, полученный из графа G в результате свертки вершины v второй степени, два соседа которой не были смежными друг другу. Тогда граф G имеет вершинное покрытие из k вершин в том и только том случае, если G’ имеет вершинное покрытие из k-1 вершины. | '''Теорема 2. Пусть G’ – граф, полученный из графа G в результате свертки вершины v второй степени, два соседа которой не были смежными друг другу. Тогда граф G имеет вершинное покрытие из k вершин в том и только том случае, если G’ имеет вершинное покрытие из k-1 вершины.''' | ||
| Строка 38: | Строка 39: | ||
== Ветвление и поиск == | == Ветвление и поиск == | ||
Самой эффективной техникой является метод ветвления и поиска, широко использовавшийся в алгоритмах решения задачи о вершинном покрытии и многих других NP-полных задач. Этот метод можно описать следующим образом. Пусть (G, k) – экземпляр задачи о вершинном покрытии. Предположим, что каким-либо образом определено семейство <math>\{ C_1, ..., C_b \} \;</math> подмножеств графа G (где для каждого i подмножество <math>C_i \;</math> имеет <math>c_i \;</math> вершин), такое, что если граф G содержит вершинное покрытие из k вершин, то по меньшей мере для одного из подмножеств <math>C_i \;</math> существует вершинное покрытие из k вершин для G, содержащее все вершины из <math>C_i \;</math>. После этого можно построить семейство экземпляров меньшего размера <math>(G_i, k_i) \;</math>, где <math>1 \le i \le b \;</math>; <math>k_i = k - c_i \;</math>, а <math>G_i \;</math> получается из G путем удаления всех вершин, входящих в <math>C_i \;</math>. Отметим, что исходный граф G имеет вершинное покрытие из k вершин в том и только том случае, если один из меньших экземпляров <math>(G_i, k_i) \;</math> графа <math>G_i \;</math> имеет вершинное покрытие из <math>k_i \;</math> вершин. Таким образом, процесс может быть разветвлен на b подпроцессов, каждый из которых на меньшем экземпляре задачи <math>(G_i, k_i) \;</math> рекурсивно выполняет поиск вершинного покрытия из <math>k_i \;</math> вершин для графа <math>G_i \;</math>. | Самой эффективной техникой является метод ветвления и поиска, широко использовавшийся в алгоритмах решения задачи о вершинном покрытии и многих других NP-полных задач. Этот метод можно описать следующим образом. Пусть (G, k) – экземпляр задачи о вершинном покрытии. Предположим, что каким-либо образом определено семейство <math>\{ C_1, ..., C_b \} \;</math> подмножеств графа G (где для каждого i подмножество <math>C_i \;</math> имеет <math>c_i \;</math> вершин), такое, что если граф G содержит вершинное покрытие из k вершин, то по меньшей мере для одного из подмножеств <math>C_i \;</math> существует вершинное покрытие из k вершин для G, содержащее все вершины из <math>C_i \;</math>. После этого можно построить семейство экземпляров меньшего размера <math>(G_i, k_i) \;</math>, где <math>1 \le i \le b \;</math>; <math>k_i = k - c_i \;</math>, а <math>G_i \;</math> получается из G путем удаления всех вершин, входящих в <math>C_i \;</math>. Отметим, что исходный граф G имеет вершинное покрытие из k вершин в том и только том случае, если один из меньших экземпляров <math>(G_i, k_i) \;</math> графа <math>G_i \;</math> имеет вершинное покрытие из <math>k_i \;</math> вершин. Таким образом, процесс может быть разветвлен на b подпроцессов, каждый из которых на меньшем экземпляре задачи <math>(G_i, k_i) \;</math> рекурсивно выполняет поиск вершинного покрытия из <math>k_i \;</math> вершин для графа <math>G_i \;</math>. | ||
Пусть T(k) – количество листьев в дереве поиска для вышеописанного процесса ветвления и поиска на экземпляре задачи (G, k). Тогда операция ветвления дает следующее рекуррентное соотношение: | Пусть T(k) – количество листьев в дереве поиска для вышеописанного процесса ветвления и поиска на экземпляре задачи (G, k). Тогда операция ветвления дает следующее рекуррентное соотношение: | ||
| Строка 56: | Строка 58: | ||
Теорема 3. Задача о вершинном покрытии может быть решена за время <math>O(kn + 1,2852^k) \;</math>. | '''Теорема 3. Задача о вершинном покрытии может быть решена за время <math>O(kn + 1,2852^k) \;</math>.''' | ||
Недавно коэффициент из теоремы 3 удалось улучшить, разработав алгоритм с временем выполнения <math>O(kn + 1,2738^k) \;</math> [4]. | Недавно коэффициент из теоремы 3 удалось улучшить, разработав алгоритм с временем выполнения <math>O(kn + 1,2738^k) \;</math> [4]. | ||
== Применение == | == Применение == | ||
| Строка 66: | Строка 69: | ||
На основе параметризованного алгоритма, упомянутого в теореме 3, был разработан более быстрый алгоритм для решения другой важной NP-полной задачи – задачи о нахождении максимального независимого множества на разреженных графах [3]. | На основе параметризованного алгоритма, упомянутого в теореме 3, был разработан более быстрый алгоритм для решения другой важной NP-полной задачи – задачи о нахождении максимального независимого множества на разреженных графах [3]. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Главный нерешенный вопрос в этом направлении исследований заключается в том, насколько далеко по нему можно зайти. Точнее говоря, насколько маленькой может быть константа c > 1, чтобы алгоритм решения задачи о вершинном покрытии имел время выполнения <math>O(c^k n^{O(1)}) \;</math>? Более тщательный анализ комбинаторных структур графов позволяет надеяться на некоторое улучшение текущей наилучшей верхней границы [4]. Несколько недавно разработанных техник [6] также обещают улучшить значение верхней границы. С другой стороны, известно, что константа c не может быть произвольно близкой к 1, за исключением определенных, редко встречающихся в теории сложности случаев [8]. | Главный нерешенный вопрос в этом направлении исследований заключается в том, насколько далеко по нему можно зайти. Точнее говоря, насколько маленькой может быть константа c > 1, чтобы алгоритм решения задачи о вершинном покрытии имел время выполнения <math>O(c^k n^{O(1)}) \;</math>? Более тщательный анализ комбинаторных структур графов позволяет надеяться на некоторое улучшение текущей наилучшей верхней границы [4]. Несколько недавно разработанных техник [6] также обещают улучшить значение верхней границы. С другой стороны, известно, что константа c не может быть произвольно близкой к 1, за исключением определенных, редко встречающихся в теории сложности случаев [8]. | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
