Mostrando que a exclusão mínima de vértice para um gráfico bipartido é NP-complete

Considere o seguinte problema cuja instância de entrada é um gráfico simples e um número inteiro natural . $G$ $k$

Existe um conjunto tal que seja bipartido e ? $S \subseteq V(G)$ $G - S$ $|S| \leq k$

Eu gostaria de mostrar que esse problema é -completo, reduzindo 3-SAT, -CLIQUE, -DOMINATING SET ou -VERTEX COVER a ele. $\rm{NP}$ $k$ $k$ $k$

Eu acredito que posso reduzir o problema das 3 CORES a ele, então eu só precisaria ver como reduzir um dos problemas mencionados. Mas, como isso seria um pouco confuso, pergunto-me se alguém vê uma redução elegante nos problemas acima mencionados.

Além disso, existe um nome para esse problema de decisão?

complexity-theory np-complete reductions Jernej
fonte

Ciclo ímpar Transversal .

Isso parece semelhante ao conjunto de vértices de feedback . Ou seja, você deseja encontrar um subconjunto mínimo de vértices para remover, de modo que o gráfico resultante seja acíclico. Um gráfico acíclico é, por definição, uma árvore (ou floresta) que é bipartida.

Nicholas Mancuso

@NicholasMancuso Não é tão parecido. É realmente como eu disse acima, o problema do Transversal do Ciclo Estranho. Ou, como Vor aponta, foi chamado de apagamento do nó bipartido (ou vértice) por Yannakakis nos anos 70 e 80.

@ PålGD, eu concordo. Eu senti que a redução mais fácil seria do FVS. No entanto, isso é desnecessário por sua definição como Odd Cycle Transversal.

Nicholas Mancuso

@Jernej: você diz "... eu gostaria de mostrar que esse problema está no NP , reduzindo-o para 3-SAT, o k-CLIQUE, ...". Você quer dizer "Gostaria de mostrar que esse problema é difícil de usar NP usando uma redução de 3-SAT, k-CLIQUE, ..."? (o problema é claramente em NP porque testando se um gráfico é bipartido pode ser feito em tempo linear)

Vor

Respostas:

Seu problema é um caso especial de uma classe mais ampla de problemas denominados problemas de exclusão de nó :

JM Lewis e M. Yannakakis, "O problema de exclusão de nós para propriedades hereditárias é NP-completo"

... Este trabalho trata da classe de problemas de gráfico definida da seguinte forma:
para uma propriedade fixa do gráfico , encontre o número mínimo de nós (ou vértices) que devem ser excluídos de um determinado gráfico para que o resultado seja satisfatório . Chamamos isso de problema de exclusão de nó para . Nossos resultados mostram que se é uma propriedade não trivial que é hereditária no subgráfico induzido, o problema de exclusão de nós para é NP-difícil. Além disso, se adicionarmos a condição de que o teste de pode ser realizado em tempo polinomial, nossos resultados implicam que o problema de exclusão de nó para $\Pi$ $G$ $\Pi$ $\Pi$ $\Pi$ $\Pi$ $\Pi$ está completo com NP. ... $\Pi$

Seu problema é o problema de exclusão de nó para a bipartidade , mas (conforme observado por Pal), hoje é conhecido como o problema de deslocamento de ciclo estranho (OCT).

EDITAR

No que diz respeito a uma redução direta, pensei nessa da 3SAT.

Dada uma instância do 3SAT com variáveis e cláusulas , construa o seguinte gráfico: adicione dois nós para cada variável e uma aresta entre eles. Para simular uma atribuição de verdade, adicione nós para cada variável e conecte-os a e ; dessa maneira, para fazer um gráfico bipartido excluir no máximo nós, pelo menos um entre e deve ser excluído. Finalmente para cada cláusula $n$ $m$ $x_i, \overline{x_i}$ $n+1$ $x_i$ $x_i$ $\overline{x_i}$ $n$ $x_i$ $\overline{x_i}$ $C_j$ adicione 4 nós e construa um ciclo ímpar que conecte as variáveis em . $C_j$

O gráfico resultante pode ser feita exclusão bipartido no máximo nodos se e apenas se a fórmula 3SAT original for satisfeita. $G$ $n$

insira a descrição da imagem aqui

Vor
fonte

Esta não é realmente a resposta que a pergunta pede. O OP deseja reduzir explicitamente usando o problema fornecido. Além disso, o problema é conhecido hoje como Odd Cycle Transversal.

21413 Pdl GD

@ PålGD: você está certo.

Vor

Sim, mas não consigo ver imediatamente uma redução na lista de problemas do OP, no entanto ... só sei o que você mencionou, de Yannakakis.

@ PålGD: Pensarei em uma redução diferente, mas, para ser sincero, não tenho certeza do que exatamente o OP quer (veja meu comentário acima).

Vor

@Vor O que eu quero é ver uma simples redução de um dos problemas mencionados. Este artigo é conhecido por mim, mas estou procurando a redução mais direta.

Jernej