Неблокирующее устройство - Википедия - Nonblocker

Множества белых вершин - максимальные неблокаторы

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

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

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

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

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

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

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

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

Рекомендации