Оценка сложности нахождения независимых вершинных разрезов для некоторых классов графов

Выполнила: Редина Лилия Александровна

В данной работе рассматриваются задачи поиска независимых вершинных разрезов в неориентированных графах с ограничениями на максимальную и минимальную степень вершины. Мы представили новый подход к задаче и новый алгоритм поиска вершинного разреза. В частности, доказали, что для графов с максимальной степенью вершины $\le 5$ наш алгоритм работает за время $O(2^{n/2}\,n^2)$, что является на данный момент лучшей оценкой для таких графов. Также показали, что для графов $O(\log n)$ компонентами и для графов с минимальной степень вершины $>n/2$ алгоритм работает за полиномиальное время. Представленная конструкция алгоритма очень перспективная и в будущем расширяется на более общий класс графов.

Задача поиска специального вершинного разреза достаточно фундаментальная, прикладная, актуальная, и пока что не такая изученная, как похожая задача о реберном разрезе. Независимые вершинные разрезы представляют собой важный инструмент при решении задач, связанных, например, с декомпозицией графов. Они позволяют разделять граф на части так, чтобы удаляемые вершины не были смежны друг с другом. Такое свойство удобно при применении методов типа "разделяй и властвуй": после удаления независимого разреза можно независимо обрабатывать получившиеся компоненты без риска возникновения новых связей между ними. Независимые разрезы также находят применение в анализе надёжности сетей, проектировании отказоустойчивых систем, теории раскрасок и других областях современной теории графов.