Аноним

Разрывающее множество вершин на неориентированном графе: различия между версиями

Материал из WEGA

Разрывающее множество вершин на неориентированном графе (посмотреть исходный код)

Версия от 14:05, 1 октября 2023

640 байт добавлено ,  1 октября 2023
м
нет описания правки
мНет описания правки
 
(не показано 10 промежуточных версий этого же участника)
Строка 10: Строка 10:




Карп [11] показал, что эта задача является NP-полной. Лунд и Янакаккис [12] доказали, что существует некоторая константа <math>\epsilon > 0 \;</math>, такая, что аппроксимация версии оптимизации UFVS с коэффициентом <math>1 + \epsilon \;</math> является NP-полной задачей. Лучший известный на данный момент алгоритм аппроксимации с полиномиальным временем выполнения имеет коэффициент 2 [1, 4]. Беккер и др. [3] предложили простой и элегантный рандомизированный алгоритм, решающий задачу UFVS за время <math>O(c \cdot 4^k \cdot kn) \;</math> на графе с n вершинами и m ребрами при помощи нахождения разрывающего множества вершин размера k с вероятностью не менее <math>1 - (1 - 4^{-k})^{c4^k} \;</math> для произвольной константы c. Точный алгоритм решения задачи UFVS с временем выполнения <math>O(1,7548^n) \;</math> недавно разработали Фомин и др. [9]. В контексте параметризованной сложности [8, 13] Бодлендер [5], а также Дауни и Феллоуз [7] первыми показали, что задача разрешима при помощи алгоритмов с фиксированными параметрами, т.е. что комбинаторный взрыв при ее решении может быть ограничен параметром k. Наилучший известный на данный момент алгоритм решения задачи UFVS с фиксированным параметром выполняется за время <math>O(c^k \cdot mn) \;</math> для константы c [6, 10] (в [6] представлен анализ наилучшего времени выполнения, имеющего место при значении константы c = 10,567). Этот алгоритм будет рассмотрен далее.
Карп [11] показал, что эта задача является NP-полной. Лунд и Янакаккис [12] доказали, что существует некоторая константа <math>\epsilon > 0 \;</math>, такая, что аппроксимация версии оптимизации UFVS с коэффициентом <math>1 + \epsilon \;</math> является NP-полной задачей. Лучший известный на данный момент аппроксимационный алгоритм с полиномиальным временем выполнения имеет коэффициент 2 [1, 4]. Беккер и др. [3] предложили простой и элегантный рандомизированный алгоритм, решающий задачу UFVS за время <math>O(c \cdot 4^k \cdot kn) \;</math> на графе с n вершинами и m ребрами при помощи нахождения разрывающего множества вершин размера k с вероятностью не менее <math>1 - (1 - 4^{-k})^{c4^k} \;</math> для произвольной константы c. Точный алгоритм решения задачи UFVS с временем выполнения <math>O(1,7548^n) \;</math> недавно разработали Фомин и др. [9]. В контексте параметризованной сложности [8, 13] Бодлендер [5], а также Дауни и Феллоуз [7] первыми показали, что задача разрешима при помощи алгоритмов с фиксированными параметрами, т.е. что комбинаторный взрыв при ее решении может быть ограничен параметром k. Наилучший известный на данный момент алгоритм решения задачи UFVS с фиксированным параметром выполняется за время <math>O(c^k \cdot mn) \;</math> для константы c [6, 10] (в [6] представлен анализ наилучшего времени выполнения, имеющего место при значении константы c = 10,567). Этот алгоритм будет рассмотрен далее.


== Основные результаты ==
== Основные результаты ==
Алгоритм решения задачи UFVS за время O(ck-mn)основан на так называемой технике «итеративного сжатия», введенной Ридом и др. [14]. Основная идея этой техники проста, но эффективна: для вывода алгоритма с фиксированным параметром для задачи минимизации достаточно задать «подпрограмму сжатия» с фиксированным параметром, которая для решения размера (k + 1) либо доказывает, что решения размера k не существует, либо строит такое решение. Начиная с тривиального экземпляра и итеративно применяя подпрограмму сжатия линейное количество раз к экземплярам большего размера, получаем алгоритм решения задачи с фиксированным параметром. Главная проблема при применении этой техники к задаче UFVS заключается в том, чтобы показать, что такая подпрограмма сжатия с фиксированным параметром существует.
Алгоритм решения задачи UFVS за время <math>O(c^k \cdot mn) \;</math> основан на так называемой технике «итеративного сжатия», введенной Ридом и др. [14]. Основная идея этой техники проста, но эффективна: для вывода алгоритма с фиксированным параметром для задачи минимизации достаточно задать «подпрограмму сжатия» с фиксированным параметром, которая для решения размера (k + 1) либо доказывает, что решения размера k не существует, либо строит такое решение. Начиная с тривиального экземпляра и итеративно применяя подпрограмму сжатия линейное количество раз к экземплярам большего размера, получаем алгоритм решения задачи с фиксированным параметром. Главная проблема при применении этой техники к задаче UFVS заключается в том, чтобы показать, что такая подпрограмма сжатия с фиксированным параметром существует.




Подпрограмма сжатия из [6, 10] работает следующим образом:
Подпрограмма сжатия, представленная в [6, 10], работает следующим образом:


1 Рассмотрим все возможные разбиения (X, Y), имеющие размер (k + 1), для разрывающего множества вершин F с jXj < k в предположении, что множество X полностью содержится в новом разрывающем множестве F0 размера k и что Y \ F0 = ;
1 Рассмотрим все возможные разбиения (X, Y), имеющие размер (k + 1), для разрывающего множества вершин F с <math>|X| \le k \;</math> в предположении, что множество X полностью содержится в новом разрывающем множестве F' размера k и что <math>Y \cap F' = \empty \;</math>.


2 Для каждого разбиения (X, Y), в случае, если вершины из Y порождают циклы, ответ для этого разбиения будет отрицательным; в противном случае следует удалить вершины из X. После э того необходимо применить следующие правила редукции данных к оставшемуся графу:
2 Для каждого разбиения (X, Y), в случае, если вершины из Y порождают циклы, ответ для этого разбиения будет отрицательным; в противном случае следует удалить вершины из X. После этого необходимо применить следующие правила редукции данных к оставшемуся графу:


• Удалить вершины степени 1.
• Удалить вершины степени 1.


• Если существует вершина степени 2 с двумя соседями v1 и v2, где v1 £ Y или v2 £ Y, то удалить v и соединить v1 и v2. Если при этом создается второе параллельное ребро между v1 и v2, удалить вершину v1 или v2, не принадлежащую к Y, и добавить ее к любому разрывающему множеству вершин для сокращенного экземпляра. Наконец, исчерпывающим образом для каждого множества вершин S сокращенного графа, размер которого не превышает k — |X|, проверить, можно ли добавить S к X для образования разрывающего множества вершин входного графа. Если такое множество вершин существует, вывести его вместе с X в качестве нового разрывающего множества вершин размера k.
• Если существует вершина степени 2 с двумя соседями <math>v_1 \;</math> и <math>v_2 \;</math>, где <math>v_1 \notin Y \;</math> или <math>v_2 \notin Y \;</math>, то удалить v и соединить <math>v_1 \;</math> и <math>v_2 \;</math>. Если при этом создается второе параллельное ребро между <math>v_1 \;</math> и <math>v_2 \;</math>, удалить вершину <math>v_1 \;</math> плюс <math>v_2 \;</math>, не принадлежащую к Y, и добавить ее к любому разрывающему множеству вершин для сокращенного экземпляра.


Наконец, исчерпывающим образом для каждого множества вершин S сокращенного графа, размер которого не превышает k — |X|, проверим, можно ли добавить S к X для образования разрывающего множества вершин входного графа. Если такое множество вершин существует, вывести его вместе с X в качестве нового разрывающего множества вершин размера k.


Корректность подпрограммы сжатия следует из ее прямолинейной природы и из корректности двух правил редукции данных, доказать которую несложно. Сложнее всего доказать, что время выполнения подпрограммы сжатия составляет O(ck-m): Существует 2k+1 разбиений множества F на вышеупомянутые подмножества (X, Y); можно показать, что для каждого разбиения сокращенный граф после выполнения правил редукции данных имеет не более d-k вершин для константного значения d; в противном случае для этого разбиения не существует разрывающего множества вершин  размера k. Таким образом, время выполнения составляет O(c'c-m). Более детальное доказательство границы размера d-k см. в [6, 10].


Корректность подпрограммы сжатия следует из ее прямолинейной природы и из корректности двух правил редукции данных, доказать которую несложно. Важнее показать, что время выполнения подпрограммы сжатия составляет <math>O(c^k \cdot m) \;</math>: существует <math>2^k + 1 \;</math> разбиений множества F на вышеупомянутые подмножества (X, Y); можно показать, что для каждого разбиения сокращенный граф после выполнения правил редукции данных имеет не более <math>d \cdot k \;</math> вершин для константного значения d; в противном случае для этого разбиения не существует разрывающего множества вершин  размера k. Таким образом, время выполнения составляет <math>O(c^k \cdot m) \;</math>. Более детальное доказательство границы размера <math>d \cdot k \;</math> см. в [6, 10].


Для входного графа G с множеством вершин fv1 ;::: ;vng алгоритм с фиксированным параметром из работ [6, 10] решает задачу UFVS путем итеративного рассмотрения подграфов Gi := G[fv1 , ... ,  vig]. Для i = 1 оптимальное разрывающее множество вершин является пустым. Предположим, что в случае i > 1 оптимальное разрывающее множество вершин Xi для Gi неизвестно. Очевидно, что Xi [ fvi+1g является искомым множеством для Gi+1. Используя подпрограмму сжатия, алгоритм за время O(ck-m) может определить, является ли Xi [ fvi+1g оптимальным разрывающим множеством вершин для Gi+1, и в случае, если оно таковым не является, вычислить оптимальное разрывающее множество вершин для Gi+1. Таким образом, в случае i = n мы получаем оптимальное разрывающее множество вершин для графа G за время O(c -mri).


Для входного графа G с множеством вершин <math>\{ v_1, ..., v_n \} \;</math> алгоритм с фиксированным параметром из работ [6, 10] решает задачу UFVS путем итеративного рассмотрения подграфов <math>G_i := G[ \{v_1, ...,  v_i \} ] \;</math>. Для i = 1 оптимальное разрывающее множество вершин является пустым. Предположим, что в случае i > 1 оптимальное разрывающее множество вершин <math>X_i \;</math> для <math>G_i \;</math> известно. Очевидно, что <math>X_i \cup \{ v_{i+1} \} \;</math> является искомым множеством для <math>G_{i+1} \;</math>. Используя подпрограмму сжатия, алгоритм за время <math>O(c^k \cdot m) \;</math> может определить, является ли <math>X_i \cup \{ v_{i+1} \} \;</math> оптимальным разрывающим множеством вершин для <math>G_{i+1} \;</math>, и в случае, если оно таковым не является, вычислить оптимальное разрывающее множество вершин для <math>G_{i+1} \;</math>. Таким образом, в случае i = n мы получаем оптимальное разрывающее множество вершин для графа G за время <math>O(c^k \cdot mn) \;</math>.


Теорема 1. Задачу нахождения разрывающего множества вершин на неориентированном графе можно решить за время O(ck-mn) для константного значения c.
 
'''Теорема 1. Задачу нахождения разрывающего множества вершин на неориентированном графе можно решить за время <math>O(c^k \cdot mn) \;</math> для константного значения c.'''


== Применение ==
== Применение ==
Задача нахождения разрывающего множества вершин на неориентированном графе имеет огромное значение для комбинаторной оптимизации. Типичным примером может служить разработка комбинаторных схем [ ]. Приложения в области задач на удовлетворение ограничений и баейсовского вывода см. в работе Бар-Йехуды и др. [2].
Задача нахождения разрывающего множества вершин на неориентированном графе имеет огромное значение для комбинаторной оптимизации. Типичным примером может служить разработка комбинаторных схем [1]. Приложения в области задач на удовлетворение ограничений и баейсовского вывода см. в работе Бар-Йехуды и др. [2].


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


== Литература ==
== Литература ==
Irina
4430

правок

Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/11669...15177