Conjunto independente em gráficos sem triângulo cúbico

Eu sei que o conjunto independente máximo em gráficos sem triângulo cúbico é NP-completo.

Ainda é NP-completo no caso de exigirmos que o conjunto independente seja do tamanho exato ?$|V|/2$

Basicamente, a instância YES de um problema de conjunto independente em gráficos sem triângulo cúbico deve ter exatamente nós . Nenhuma instância possui um conjunto independente de tamanho menor que .$|V|/2$$|V|/2$

Vamos começar provando que o conjunto independente máximo tem tamanho máximo de . Deixe- ser um conjunto independente. Para cada vértice , vamos ser o número de seus vizinhos em . Se , então sabemos que . Como o gráfico é cúbico,. Desde , o número de vértices tais que é pelo menos. Daí .$|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$

Quando podemos ter igualdade? Devemos ter , por isso, para cada vértice não em , todos os seus vizinhos devem estar em . O inverso também é verdadeiro - para cada vértice em , todos os seus vizinhos não estão em . Em outras palavras, o gráfico deve ser bipartido. Isso pode ser verificado em tempo polinomial.$\alpha(v) \in \{0,3\}$$I$$I$$I$$I$