Minimale Dreiecksabdeckungen

Wie viele Kanten von müssen bei einem Diagramm mindestens gelöscht werden, um das Diagrammdreieck frei zu machen? Für mein ungeübtes Auge scheint dies ein schwieriges Problem zu sein.$G$$G$

Ist bekannt, dass dieses Problem NP-vollständig ist? Was ist mit dem Analogon für orientierte Graphen (dh Digraphen ohne parallele Kanten) und gerichtete 3-Zyklen? Referenzen wären sehr dankbar!

EDIT: David hat meine Frage im ungerichteten Fall unten sehr hilfreich beantwortet. Alle Informationen über die gerichtete / orientierte Version wäre sehr dankbar.

Die ungerichtete Version ist NP-hart. Insbesondere ist das folgende Problem, das als partieller Rückkopplungskantensatz bekannt ist, NP-vollständig: Wenn ein ungerichteter Graph  und positive ganze Zahlen K und L gegeben sind , gibt es einen Satz von höchstens K  Kanten, der mindestens eine Kante aus jedem Zyklus von enthält Länge höchstens  L in  G . Dies ist für jedes feste L ≥ 3 immer noch NP-vollständig , und wenn G  auf zweiteilig beschränkt ist (in diesem Fall kann L  auch auf einen beliebigen Wert von mindestens  4 festgelegt werden ).$G$$K$$L$$K$$L$$G$$L\geq 3$$G$$L$$4$

$4$$k$$4$

Quellen: Die ungerichtete Version ist das Problem GT9 von Garey und Johnson, Computer und Intraktabilität (Freeman, New York, 1979). Das Originalpapier war Yannakakis, Node- und Edge-Deletion-NP-vollständige Probleme (Proceedings of STOC 1978), aber es scheint keinen Beweis zu enthalten. Karps Beweis für das Feedback Arc Set befindet sich auf der Seite des Papiers "21 Probleme": Reduzierbarkeit zwischen kombinatorischen Problemen (Proceedings of Symposium on Complexity of Computer Computations, 1972).