Структурные и алгоритмические свойства максимальных диссоциирующих множеств в графах

Труды института математики и механики УрО РАН. 2022. Т. 28. № 2. С. 114–142.

Дугинов О. И., Кускова Б. М., Малышев Д. С., Шур Н. А.

Подмножество вершин графа называется диссоциирующим, если степени вершин подграфа, порожденного этим подмножеством, не превосходят 1. Диссоциирующее множество максимально, если оно не содержится ни в каком другом диссоциирующем множестве с бо́льшим числом вершин. В данной работе предлагаются оценки наибольшего (наименьшего) числа вершин в максимальном диссоциирующем множестве графа. Доказано, что задача нахождения максимального диссоциирующего множества наибольшей мощности NP-трудна для квазихордальных двудольных графов. Кроме этого доказано, что задача нахождения максимального диссоциирующего множества наименьшей мощности NP-трудна для хордальных двудольных графов, двудольных графов с максимальной степенью вершин, равной 3, планарных графов с большим обхватом, а также для классов графов, характеризуемых конечными списками запрещенных порожденных двусвязных подграфов. Предлагается линейный алгоритм решения последней задачи в классе деревьев.

Ключевые слова: наследственные классы графов, NP-полнота, деревья, максимальное диссоциирующее множество графа, задача поиска наибольшего порожденного подграфа с максимальной степенью вершин не больше 1,, максимальное диссоциирующее множество, квазихордальные двудольные графы