Независимый набор на кубических треугольных свободные график

Я знаю, что максимальное независимое множество на кубических графах без треугольников является NP-полным.

Является ли он еще NP-полным, если нам требуется, чтобы независимый набор имел размер точно ?$|V|/2$

В основном, ДА экземпляр задачи о независимом множестве в задаче о кубах без треугольников должен иметь ровно узлов. НЕТ экземпляра имеет независимый набор размером меньше, чем .$|V|/2$$|V|/2$

Давайте начнем с доказательства того, что максимальное независимое множество имеет размер не более . Пусть независимое множество. Для каждой вершины , пусть будет число его соседей в . Если , то мы знаем , что . Поскольку граф является кубической,, Так , число вершин , таких , что , по крайней мере, Следовательно .$|V|/2$$I$$v$$\alpha(v)$$I$$\alpha(v) \geq 1$$v \notin I$$\sum_v \alpha(v) = 3|I|$$\alpha(v) \leq 3$$\alpha(v) \geq 1$$|I|$$|I| \leq |V|/2$

Когда мы можем достичь равенства? Мы должны иметь , поэтому для каждой вершины не в , все его соседи должны быть в . Обратное также верно - для каждой вершины , все его соседи не . Другими словами, график должен быть двудольным. Это можно проверить за полиномиальное время.$\alpha(v) \in \{0,3\}$$I$$I$$I$$I$