Conjunto independiente en gráficos sin triángulos cúbicos

Sé que el conjunto independiente máximo en gráficos sin triángulos cúbicos es NP-completo.

¿Sigue siendo NP completo en caso de que necesitemos que el conjunto independiente sea de tamaño exactamente ?$|V|/2$

Básicamente, la instancia SÍ de un problema de conjunto independiente en un gráfico de gráficas libres de triángulos cúbicos debe tener exactamente nodos. NINGUNA instancia tiene un conjunto independiente de tamaño menor que .$|V|/2$$|V|/2$

Comencemos demostrando que el conjunto independiente máximo es de tamaño como máximo . Let ser un conjunto independiente. Para cada vértice , deje sea el número de sus vecinos en . Si , entonces sabemos que . Como el gráfico es cúbico,. Como , el número de vértices de manera que es al menos. Por lo tanto .$|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$

¿Cuándo podemos tener igualdad? Debemos tener , por lo que para cada vértice no en , todos sus vecinos deben estar en . Lo contrario también es cierto - para cada vértice en el , todos sus vecinos no están en . En otras palabras, el gráfico debe ser bipartito. Esto puede verificarse en tiempo polinómico.$\alpha(v) \in \{0,3\}$$I$$I$$I$$I$