O problema do conjunto de vértices de feedback nos gráficos de graus delimitados planares é difícil?

Respostas:

16

De acordo com o livro de Garey e Johnson, Vertex Cover é NP-completo em gráficos planares de grau máximo quatro. O uso de uma redução simples de Vertex Cover para Feedback Vertex Set deve fornecer o grau máximo oito e preservar a planaridade.

VC para FVS: Substitua cada aresta por um triângulo (ou uma aresta dupla).

Uma observação: Garey e Johnson também afirmam que o FVS direcionado é NP-completo em dígrafos planares com nenhum grau superior ou igual a dois. Eles não mencionam especificamente o FVS não direcionado sob essas restrições.

Stefan Kratsch
fonte
14

4

4

A restrição de grau é a melhor possível, pois a FVS é polinomial para gráficos de grau máximo no máximo três; veja aqui .

Edit: O graphclasses.org de Ernst de Ridder agora contém todas as informações disponíveis sobre o FVS; incluindo cerca de 550 polinomialmente solucionáveis ​​e cerca de 250 casos de NP-c.

vb le
fonte
você poderia explicar mais sobre a redução, que está longe de ser clara para mim. Não tenho a tese de Speckenmeyer em mãos (mesmo que eu tivesse, não poderei entender alemão). Mas eu tenho o artigo que você mencionou, que, no entanto, refere-se apenas à sua tese. Por outro lado, eu sei que é NP-difícil em gráficos gerais de grau máximo 4, como mostrado por Romeo Rizzi doi.org/10.1007/s00453-007-9112-8 . Obrigado!
Yixin Cao
5

De acordo com a Wikipedia, a Garey & Johnson também mostrou que "a cobertura de vértices permanece NP-completa ... mesmo em gráficos planares de grau no máximo 3."

Assim, o FVS é difícil em gráficos planares com grau máximo 6.

101011
fonte
2

Aparentemente, na tese de doutorado de Speckenmeyer, ele demonstra que o problema do conjunto de vértices de feedback é NP-difícil para gráficos de grau máximo 4. Essa afirmação aparece aqui , por exemplo.

n/2−z(G)+1nzz(G)G

Edit: não examinou a edição do vb le com bastante cuidado ...

Timothy Sun
fonte