¿El problema del conjunto de vértices de retroalimentación es solucionable en tiempo polinómico para gráficos limitados de 3 grados?

19

Feedback Vertex Set es NP-complete para gráficos generales. Se sabe que es NP-completo para gráficos limitados de grado 8 debido a una reducción de la cubierta del vértice. El artículo de Wikipedia dice que es polisoluble para gráficos limitados de grado 3 y NP-completo para gráficos limitados de grado 4. Pero no he podido encontrar ninguna prueba de esto en ningún lado. ¿Es verdad?

¿Cuál es el mínimo d tal que FVS en los gráficos acotados de grado d es NP-completo?

cc.complexity-theory graph-theory graph-algorithms np-hardness bounded-degree Davis Issac
fuente
1
¿Alguien sabe si el problema es difícil en los gráficos regulares no dirigidos de grado 4?

Respuestas:

10

El algoritmo de Li y Liu es incorrecto (está publicado en China, aunque en inglés). El algoritmo de Ueno et al. Es correcto, y un algoritmo similar se puede encontrar en Furst et al. 1 . Ambos algoritmos reducen el problema al problema de paridad matroide polinomio-solucionable [3].

¡Su reducción de VC garantiza la dureza NP para el gráfico acotado de grado 6! Como VC ya es NP-hard en gráficos cúbicos. Speckenmeyer ha afirmado que su tesis [4] contiene la prueba de la dureza NP de FVS en gráficos planos de grado máximo cuatro, pero es muy difícil de encontrar (agradeceré mucho si quien tiene acceso a su tesis puede enviarme una copia ) Afortunadamente, se puede encontrar una nueva prueba de la dureza NP de los gráficos acotados de grado cuatro en 2 :

Observaciones sobre 2 : - De hecho, demostró que el problema es APX-hard, pero es fácil verificar que sus reducciones también son válidas para la prueba de NP-hardness del problema. - Su reducción NO se aplica a los gráficos planos.

  1. Merrick L. Furst, Jonathan L. Gross y Lyle A. McGeoch, "Encontrando una incrustación gráfica de máximo género", Journal of the ACM, vol. 35, no. 3, págs. 523–534, 1988. 10.1145 / 44483.44485
  2. Rizzi, R .: Las bases del ciclo débilmente fundamentales son difíciles de encontrar. Algorithmica 53 (3), 402-424 (2009) 10.1007 / s00453-007-9112-8
  3. László Lovász, "El problema de la correspondencia matroide", en Métodos algebraicos en teoría de grafos, ser. Coloquios Mathematica Societatis János Bolyai, vol. 25, Szeged, Hungría, 1980, págs. 495–517.
  4. Ewald Speckenmeyer, "El problema del vértice de retroalimentación Untersuchungen zum en ungerichteten graphen", tesis doctoral, Universität-GH Paderborn, Reihe Informatik, Bericht, 1983.
Yixin Cao
fuente
99
¿Hay una razón simple por la que es "claramente incorrecto"?
Suresh Venkat
2
@SureshVenkat Perdón por la respuesta tardía: acabo de notar esta pregunta. El error crítico está en el Teorema 4.2, que es el teorema principal de este artículo. Se afirma que dado un juego de adyacencia y un par de bordes { e 1 , e 2 } en una más grande de adyacencia coincidente M ' pero no en M , que pueden aumentar M mediante la adición de { e 1 , e 2 } a M . Esto es claramente incorrecto, porque la definición de coincidencia de adyacencia requiere la eliminación de todos los bordes de una coincidencia de adyacencia NO desconecta el gráfico.METRO{mi1,mi2}METRO′METROMETRO{mi1,mi2}METRO
Yixin Cao
continúa ... Uno puede obtener fácilmente una coincidente con solo un par, que se encuentra en el vértice v , y otra M ' coincidente de dos pares, uno de los cuales utiliza el otro incidente de borde para v . Este par no se puede utilizar para aumentar M . Además, Lemma 4.1 también contiene errores críticos, pero no recuerdo los detalles en este momento. (Los detecté a principios de 2009, e intenté contactar a los autores de inmediato, pero desafortunadamente nunca obtuve ninguna respuesta).METROvMETRO′vMETRO
Yixin Cao
9

Las referencias relevantes parecen ser:

Ueno, Shuichi; Kajitani, Yoji; Gotoh, Shin'ya. En el problema de conjunto independiente no separado y el problema de conjunto de retroalimentación para gráficos sin un grado de vértice superior a tres. Actas de la Primera Conferencia de Japón sobre Teoría de Gráficos y Aplicaciones (Hakone, 1986). Matemáticas discretas. 72 (1988), no. 1-3, 355–360 .

Li, Deming; Liu, Yanpei. Un algoritmo polinomial para encontrar el conjunto mínimo de vértices de retroalimentación de un gráfico simple de 3 regulares. Acta Math. Sci. 19 (1999), no. 4, 375–381.

(Advertencia: no he leído ninguno de los dos, pero ambos afirman que resuelven el problema en tiempo polinómico. No creo que la diferencia entre 3-regular y máximo grado tres sea importante para este problema).

David Eppstein
fuente