Cubiertas Triángulo Mínimas

8

Dado un gráfico , ¿cuál es el número mínimo de bordes de que necesitamos eliminar para liberar el triángulo del gráfico? Para mi ojo inexperto, esto parece ser un problema difícil.solsol

¿Se sabe que este problema es NP completo? ¿Qué pasa con el análogo para gráficos orientados (es decir, dígrafos sin bordes paralelos) y 3 ciclos dirigidos? ¡Las referencias serían muy apreciadas!

EDITAR: David ha respondido muy útilmente mi pregunta, en el caso no dirigido, a continuación. Cualquier información sobre la versión dirigida / orientada sería muy apreciada.

BPN
fuente

Respuestas:

12

La versión no dirigida es NP-hard. Más específicamente, el siguiente problema, conocido como Partial Feedback Edge Set es NP-complete: dado un gráfico no dirigido  , y los enteros positivos K y L , ¿hay un conjunto de K como máximo  que contenga al menos un borde de cada ciclo de longitud como máximo  L en  G . Esto sigue siendo NP completo para cualquier L 3 fijo , y si G  está restringido a ser bipartito (en cuyo caso, L  también puede ser fijo a cualquier valor de al menos  4 ).solKLKLsolL3solL4 4

4 4k4 4

Fuentes: La versión no dirigida es el problema GT9 de Garey y Johnson, Computers and Intractability (Freeman, Nueva York, 1979). El documento original era Yannakakis, problemas de NP completo de eliminación de nodos y bordes (Procedimientos de STOC 1978) pero no parece contener una prueba. La prueba del conjunto de retroalimentación de Karp se encuentra en la página del documento "21 problemas": Reducibilidad entre problemas combinatorios (Actas del simposio sobre la complejidad de las computadoras, 1972).

David Richerby
fuente
¡Muchas gracias! (Cuando busqué en Google este problema, no tenía idea de con qué calificar el "conjunto de borde de retroalimentación" para encontrar esto.)
BPN