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.
¿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.