Неблокирующий

Белые множества вершин являются максимальными неблокаторами.

В теории графов неблокировщик — это подмножество вершин неориентированного графа , все из которых смежны с вершинами вне этого подмножества. Эквивалентно, неблокирующий является дополнением множества доминирующего . ^[1]

Вычислительная задача поиска наибольшего неблокирующего графа была сформулирована Пападимитриу и Яннакакисом (1991) , которые заметили, что он принадлежит MaxSNP . ^[2] Хотя вычисление доминирующего набора не является решаемым с фиксированными параметрами при стандартных предположениях, дополнительная проблема поиска неблокирующего набора заданного размера разрешима с фиксированными параметрами. ^[1]

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

Кернелизация

Один из способов создания управляемого алгоритма с фиксированными параметрами для неблокирующей проблемы — использовать кернеризацию — принцип алгоритмического проектирования, в котором алгоритм с полиномиальным временем используется для сведения более крупного экземпляра задачи к эквивалентному экземпляру, размер которого ограничен функцией параметр. Для неблокирующей задачи входные данные задачи представляют собой граф $G$ и параметр $k$ , и цель состоит в том, чтобы определить, является ли $G$ имеет неблокирующий блокировщик с $k$ или более вершин. ^[1]

Эта проблема имеет простую кернеризацию, которая сводит ее к эквивалентной задаче с не более чем $2k$ вершины. Сначала удалите все изолированные вершины из $G$ , поскольку они не могут быть частью какого-либо неблокирующего устройства. Как только это будет сделано, оставшийся граф должен иметь неблокирующий элемент, включающий не менее половины его вершин; например, если раскрашено в два цвета любое остовное дерево графа , каждый класс цвета является неблокирующим, и один из двух классов цвета включает в себя как минимум половину вершин. Следовательно, если граф с удаленными изолированными вершинами все еще имеет $2k$ или более вершин, проблема может быть решена немедленно. В противном случае оставшийся граф является ядром с не более чем $2k$ вершины. ^[1]

Дене и др. улучшил это до максимального размера ядра ${\tfrac {5}{3}}k+3$ . Их метод включает в себя объединение пар соседей вершин первой степени до тех пор, пока все такие вершины не будут иметь одного соседа, и удаление всех вершин первой степени, кроме одной, оставляя эквивалентный экземпляр. только с одной вершиной степени одна. Затем они показывают, что (за исключением малых значений $k$ , который можно обрабатывать отдельно) этот экземпляр должен быть либо меньше установленного размера ядра, либо содержать $k$ -блокировщик вершин. ^[1]

Как только небольшое ядро получено, экземпляр проблемы неблокирования может быть решен за приемлемое время с фиксированными параметрами путем применения поиска методом грубой силы к ядру алгоритма . Применение более быстрых (но все же экспоненциальных) оценок времени приводит к оценке времени для неблокирующей задачи вида $O(2.5154^{k}+n)$ . Для некоторых специальных классов графов возможны еще более быстрые алгоритмы. ^[1]

См. также

Доминирующий набор – дополнение неблокирующего.

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и ^ж Дене, Франк; Ребята, Майкл; Фернау, Хеннинг; Прието, Елена ; Розамонд, Фрэнсис (2006), «Неблокирующий: параметризованная алгоритмика для минимального доминирующего набора» (PDF) , SOFSEM 2006: 32-я конференция по текущим тенденциям в теории и практике информатики, Мерин, Чешская Республика, 21-27 января 2006 г., материалы , Конспекты лекций по информатике, вып. 3831, Springer, стр. 237–245, номер документа : 10.1007/11611257_21.
^ Пападимитриу, Христос Х .; Яннакакис, Михалис (1991), «Классы оптимизации, аппроксимации и сложности», Журнал компьютерных и системных наук , 43 (3): 425–440, doi : 10.1016/0022-0000(91)90023-X , MR 1135471
^ Оре, Эйстейн (1962), Теория графов , Публикации коллоквиума Американского математического общества, том. 38, Провиденс, Род-Айленд: Американское математическое общество, теорема 13.1.5, стр. 38. 207, МР 0150753

[dffpr-1] Jump up to: ^а ^б ^с ^д ^и ^ж Дене, Франк; Ребята, Майкл; Фернау, Хеннинг; Прието, Елена ; Розамонд, Фрэнсис (2006), «Неблокирующий: параметризованная алгоритмика для минимального доминирующего набора» (PDF) , SOFSEM 2006: 32-я конференция по текущим тенденциям в теории и практике информатики, Мерин, Чешская Республика, 21-27 января 2006 г., материалы , Конспекты лекций по информатике, вып. 3831, Springer, стр. 237–245, номер документа : 10.1007/11611257_21.

[py-2] Пападимитриу, Христос Х .; Яннакакис, Михалис (1991), «Классы оптимизации, аппроксимации и сложности», Журнал компьютерных и системных наук , 43 (3): 425–440, doi : 10.1016/0022-0000(91)90023-X , MR 1135471

[o-3] Оре, Эйстейн (1962), Теория графов , Публикации коллоквиума Американского математического общества, том. 38, Провиденс, Род-Айленд: Американское математическое общество, теорема 13.1.5, стр. 38. 207, МР 0150753

[1]

[2]

[3]