O problema do conjunto de vértices de feedback é solucionável em tempo polinomial para gráficos delimitados de 3 graus?

19

Feedback Vertex Set é NP-complete para gráficos gerais. É conhecido por ser NP-completo para gráficos limitados ao grau 8 devido a uma redução da cobertura de vértices. O artigo da Wikipedia diz que é poli-tempo solucionável para gráficos com limite de grau 3 e é NP completo para gráficos com limite de grau 4. Mas não consegui encontrar nenhuma prova disso em nenhum lugar. É verdade?

Qual é o valor mínimo d de tal modo que o FVS nos gráficos delimitados por graus d é NP-completo?

cc.complexity-theory graph-theory graph-algorithms np-hardness bounded-degree Davis Issac
fonte
11
Alguém sabe se o problema está nos gráficos regulares não direcionados do grau 4?

Respostas:

10

O algoritmo de Li e Liu está incorreto (é publicado na China, embora em inglês). O algoritmo de Ueno et al. Está correto, e um algoritmo semelhante pode ser encontrado em Furst et al. 1 . Ambos os algoritmos reduzem o problema ao problema de paridade matróide polinomial-solucionável [3].

Sua redução do VC garante a dureza NP para o gráfico delimitado de grau 6! Como o VC já é NP-hard em gráficos cúbicos. Speckenmeyer afirmou que sua tese [4] contém a prova da dureza NP da FVS em gráficos planares de grau máximo quatro, mas é muito difícil de encontrar (eu aprecio muito se quem tem acesso à sua tese pode me enviar uma cópia ) Felizmente, uma nova prova da dureza NP dos gráficos com limite de quatro graus pode ser encontrada em 2 :

Comentários sobre 2 : - De fato, ele provou que o problema é difícil para APX, mas é fácil verificar que suas reduções também são válidas para a prova de dureza NP do problema. - Sua redução NÃO se aplica a gráficos planares.

  1. Merrick L. Furst, Jonathan L. Gross e Lyle A. McGeoch, "Encontrando uma incorporação de gráfico de gênero máximo", Journal of the ACM, vol. 35, n. 3, pp. 523-534, 1988. 10.1145 / 44483.44485
  2. Rizzi, R .: Bases de ciclos fracamente fundamentais são difíceis de encontrar. Algoritmica 53 (3), 402-424 (2009) 10.1007 / s00453-007-9112-8
  3. László Lovász, “O problema da correspondência matróide”, em Métodos Algébricos em Teoria dos Grafos, ser. Colloquia Mathematica Societatis János Bolyai, vol. 25, Szeged, Hungria, 1980, pp. 495-517.
  4. Ewald Speckenmeyer, “Untersuchungen zum feedback vértices definem problemas em grafos ungerichteten”, tese de doutorado, Universität-GH Paderborn, Reihe Informatik, Bericht, 1983.
Yixin Cao
fonte
9
Existe uma razão simples para ser "claramente incorreto"?
Suresh Venkat
2
@SureshVenkat Desculpe pela resposta tardia: acabei de perceber esta pergunta. O erro crítico está no Teorema 4.2, que é o principal teorema deste artigo. Alega que, dada uma adjacência correspondência e um par de bordas em um maior adjacência correspondência , mas não em , eles podem aumentar adicionando para . Isso está claramente errado, porque a definição de correspondência de adjacência requer a exclusão de todas as arestas de uma correspondência de adjacência NÃO desconectou o gráfico. { e 1 , e 2 } M ′ M M { e 1 , e 2 } MM{e1,e2}M′MM{e1,e2}M
Yixin Cao
continua ... Pode-se facilmente obter um correspondente com apenas um par, que se encontra no vértice , e outro correspondente de dois pares, um dos quais usa o outro incidente da aresta para . Este par não pode ser usado para aumentar . Além disso, o Lema 4.1 também contém erros críticos, mas não me lembro dos detalhes nesse momento. (I detectado los no início de 2009, e eu tentei entrar em contato com os autores imediatamente, mas infelizmente eu nunca recebi qualquer resposta.)v M ′ v MMvM′vM
Yixin Cao
9

As referências relevantes parecem ser:

Ueno, Shuichi; Kajitani, Yoji; Gotoh, Shin'ya. No problema do conjunto independente não separável e no problema do conjunto de feedback para gráficos sem grau de vértice superior a três. Anais da Primeira Conferência do Japão sobre Teoria e Aplicações de Gráficos (Hakone, 1986). Matemática discreta. 72 (1988), n. 1-3, 355–360 .

Li, Deming; Liu, Yanpei. Um algoritmo polinomial para encontrar o conjunto de vértices de feedback mínimo de um gráfico simples de três regulares. Acta Math. Sci. 19 (1999), n. 4, 375-381.

(Aviso: eu não li nenhum deles, mas ambos afirmam resolver o problema em tempo polinomial. Não acho que a diferença entre o 3º e o 3º grau seja importante para esse problema.)

David Eppstein
fonte