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

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