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|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|V|/2|V|/2
cs.stackexchange.com/questions/1176/… pode ser relevante.
Quais são as instâncias de NO?
@YuvalFilmus Ele está perguntando se o problema éα(G)=|G|/2α(G)=|G|/2 ondeé a ordem do gráfico. Deve ser possível inserir alguns vértices isolados no gráfico para aumentar o número de independência. Mohammad, você conhece a redução? Não é possível adicionar vértices isolados para obter a redução desejada? |G||G|n/2−kn/2−k
Não, não tenho redução.
@ PålGD A redução não funcionaria, pois o problema usual pergunta se vez de . De fato, nem está claro se o problema está no NP. α(G)≥kα(G)≥kα(G)=kα(G)=k
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|V|/2IIvvα(v)α(v)IIα(v)≥1α(v)≥1v∉Iv∉I∑vα(v)=3|I|∑vα(v)=3|I|α(v)≤3α(v)≤3α(v)≥1α(v)≥1|I||I||I|≤|V|/2|I|≤|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.α(v)∈{0,3}α(v)∈{0,3}IIIIIIII