В теории графов неблокирующий элемент — это подмножество вершин в неориентированном графе , все из которых смежны с вершинами вне подмножества. Эквивалентно, неблокирующий элемент — это дополнение доминирующего множества . [1]
Вычислительная задача поиска наибольшего неблокирующего элемента в графе была сформулирована Пападимитриу и Яннакакисом (1991), которые заметили, что она принадлежит MaxSNP . [2] Хотя вычисление доминирующего множества не является разрешимой с фиксированными параметрами при стандартных предположениях, дополнительная задача поиска неблокирующего элемента заданного размера является разрешимой с фиксированными параметрами. [1]
В графах без изолированных вершин каждый максимальный неблокирующий элемент (тот, к которому нельзя добавить больше вершин) сам по себе является доминирующим множеством. [3]
Один из способов построения фиксированного параметрического трактуемого алгоритма для неблокирующей проблемы — использовать кернелизацию , алгоритмический принцип проектирования, в котором полиномиальный алгоритм используется для сокращения большего экземпляра проблемы до эквивалентного экземпляра, размер которого ограничен функцией параметра. Для неблокирующей проблемы входные данные для задачи состоят из графа и параметра , а цель состоит в том, чтобы определить, имеет ли неблокирующийся с или более вершинами. [1]
Эта проблема имеет простую кернелизацию, которая сводит ее к эквивалентной проблеме с не более чем вершинами. Сначала удалите все изолированные вершины из , так как они не могут быть частью какого-либо неблокирующего элемента. После того, как это будет сделано, оставшийся граф должен иметь неблокирующий элемент, который включает по крайней мере половину его вершин; например, если кто-то раскрашивает в 2 цвета любое остовное дерево графа, каждый цветовой класс является неблокирующим элементом, и один из двух цветовых классов включает по крайней мере половину вершин. Следовательно, если граф с удаленными изолированными вершинами все еще имеет или более вершин, проблема может быть решена немедленно. В противном случае оставшийся граф является ядром с не более чем вершинами. [1]
Dehne et al. улучшили это до ядра размером не более . Их метод включает слияние пар соседей вершин степени один до тех пор, пока все такие вершины не будут иметь одного соседа, и удаление всех вершин степени один, кроме одной, оставляя эквивалентный экземпляр только с одной вершиной степени один. Затем они показывают, что (за исключением малых значений , которые могут быть обработаны отдельно) этот экземпляр должен быть либо меньше, чем ограничение размера ядра, либо содержать блокировщик вершины. [1]
После получения небольшого ядра пример неблокируемой проблемы может быть решен за фиксированное параметрическое время, применяя алгоритм поиска методом грубой силы к ядру. Применение более быстрых (но все еще экспоненциальных) временных ограничений приводит к временному ограничению для неблокируемой проблемы вида . Для некоторых специальных классов графов возможны еще более быстрые алгоритмы. [1]
