Transitives Feedback Arc Set (TFAS): NP-vollständig?

Vor einiger Zeit habe ich eine Referenzanfrage für Diagrammprobleme gesendet, in der wir eine 2-Partition der Kanten finden möchten, bei der beide Mengen eine Eigenschaft erfüllen, die nicht mit ihrer Kardinalität zusammenhängt. Ich habe versucht zu beweisen, dass das folgende Problem NP-schwer ist:

Gibt es bei einem Turnier einen Rückkopplungsbogensatz F ⊆ E in G , der eine transitive Beziehung definiert?$G = (V,E)$$F \subseteq E$$G$

Ich habe eine Konstruktion für einen Versuch, einen Beweis zu erbringen, aber es scheint, dass dies in eine Sackgasse führen wird. Ich dachte, ich könnte hier nachfragen, ob mir etwas Offensichtliches fehlt. Um Ihre Kreativität nicht auf Gedankengänge zu beschränken, die denen ähneln, die ich verwendet habe, werde ich meinen Versuch hier nicht veröffentlichen.

Ist das Problem NP-schwer? Wenn ja, wie kann man das beweisen?

Um einen kleinen Kontext hinzuzufügen, hier ist eine Konstruktion für ein Diagramm, für das kein Transitiver Rückkopplungsbogen festgelegt ist. Für diese Konstruktion verwende ich das folgende Gadget-Diagramm:

Dieses Turnier hat die folgenden Eigenschaften (die ich mit einem Programm überprüft habe, aber formal nicht bewiesen habe):

• wenn (2,7) nicht in einem gegebenen TFAS ist, dann ist (1,3)
• wenn (5,1) in einem gegebenen TFAS ist, dann ist es (3,6)
• wenn (7,3) in einem gegebenen TFAS ist, dann ist (5,1) nicht

oder leicht missbräuchliche Prädikatlogiknotation:

• $\neg (2,7) \rightarrow (1,3)$
• $(5,1) \rightarrow (3,6)$
• $(7,3) \rightarrow \neg (5,1)$

Sie werden feststellen, dass die beiden Kanten für jede Implikation paarweise nicht verbunden sind, sodass die folgende Konstruktion funktioniert:

$A$

Ich führte ein kurzes Clingo-Programm aus, das keine Grafik ohne TFAS meldete, aber es gab einen Fehler. Ich habe es behoben und nun wird überprüft, ob es für n = 8 oder weniger keine Grafik ohne TFAS gibt. Für n = 9 findet es dieses:

is_edge(edge(2,3)) is_edge(edge(1,4)) is_edge(edge(2,4)) is_edge(edge(3,5)) is_edge(edge(4,5)) is_edge(edge(1,6)) is_edge(edge(2,6)) is_edge(edge(3,6)) is_edge(edge(5,6)) is_edge(edge(1,7)) is_edge(edge(4,7)) is_edge(edge(5,7)) is_edge(edge(6,7)) is_edge(edge(1,8)) is_edge(edge(3,8)) is_edge(edge(4,8)) is_edge(edge(5,9)) is_edge(edge(6,9)) is_edge(edge(7,9)) is_edge(edge(2,1)) is_edge(edge(3,1)) is_edge(edge(4,3)) is_edge(edge(5,1)) is_edge(edge(5,2)) is_edge(edge(6,4)) is_edge(edge(7,2)) is_edge(edge(7,3)) is_edge(edge(8,2)) is_edge(edge(8,5)) is_edge(edge(8,6)) is_edge(edge(8,7)) is_edge(edge(9,1)) is_edge(edge(9,2)) is_edge(edge(9,3)) is_edge(edge(9,4)) is_edge(edge(9,8))

Hier ist die (feste) Kodierung

% tfas.asp
#show is_edge/1.
vertex(1..n).

opp_edges(edge(A,B),edge(B,A)) :- vertex(A), vertex(B), A < B.
possible_edge(E1;E2) :- opp_edges(E1,E2).

{is_edge(E1); is_edge(E2)} = 1 :- opp_edges(E1, E2).
ntfas(E) :- possible_edge(E), not is_edge(E).
ntfas(edge(X, X)) :- vertex(X).

tfas(E) | fs(E) :- is_edge(E).
ntfas(E) :- fs(E).

broken :- ntfas(edge(A,C)), tfas(edge(A, B)), tfas(edge(B,C)).

reachable(X, Y) :- fs(edge(X, Y)), is_edge(edge(X, Y)).
reachable(X, Z) :- reachable(X, Y), fs(edge(Y, Z)), is_edge(edge(Y, Z)).
broken :- reachable(X, X).

tfas(E) :- broken, possible_edge(E).
fs(E) :- broken, possible_edge(E).
:- not broken.

Führen Sie es mit clingo -c n=7 tfas.asp(mit Clingo 4.2.1)

(das n = 7 zeigt Graphen von genau 7 Eckpunkten an)

Es sollte dann und nur dann zufriedenstellend sein, wenn auf 7 Eckpunkten ein Graph ohne TFAS existiert.

Ok, ich habe herausgefunden, welches Diagramm @ G.Bach beschreibt, und es im Clingo codiert (siehe die folgende Clingo-Beschreibung. Es beginnt mit einer Beschreibung des Gadget-Diagramms und wird fortgesetzt, um zu beschreiben, wie Kopien davon zusammengefügt werden, um das Ganze zu erhalten 34-Vertex-Turniergrafik, die G.Bach beschreibt. Ich habe auch die geerdete Grafikbeschreibung angehängt.

Ich fuhr dann fort, Clingo auf diesem Diagramm auszuführen, und es behauptete, ein TFAS mit 241 Kanten gefunden zu haben. Aber ich habe einen Fehler in der Grafikkodierung gemacht. Ich habe den Fehler behoben und Clingo meldet nun Unbefriedigendes (dh es gibt kein TFAS).

Hier ist das Programm zum Auffinden von TFAS in einer Grafik

{tfas(E)} :- is_edge(E).
:- not tfas(edge(A,C)), tfas(edge(A, B)), tfas(edge(B,C)).

reachable(X, Y) :- not tfas(edge(X, Y)), is_edge(edge(X, Y)).
reachable(X, Z) :- reachable(X, Y), not tfas(edge(Y, Z)), is_edge(edge(Y, Z)).
:- reachable(X, X).

tfas_count(N) :- N = #count{tfas(E) : tfas(E)}.

#show tfas/1.
#show tfas_count/1.

Hier ist das (aktualisierte) Programm zum Generieren von G.Bachs Grafik. Ich habe am Ende Indikatoren hinzugefügt, um zu überprüfen, ob es sich bei der Grafik um eine wohlgeformte Turniergrafik handelt:

gadget_vertex(0..7).

gadget_edge(0,1).
gadget_edge(0,2).
gadget_edge(0,3).
gadget_edge(0,4).
gadget_edge(1,2).
gadget_edge(1,3).
gadget_edge(1,6).
gadget_edge(1,7).
gadget_edge(2,3).
gadget_edge(2,4).
gadget_edge(2,5).
gadget_edge(2,7).
gadget_edge(3,4).
gadget_edge(3,5).
gadget_edge(3,6).
gadget_edge(4,1).
gadget_edge(4,5).
gadget_edge(4,6).
gadget_edge(4,7).
gadget_edge(5,0).
gadget_edge(5,1).
gadget_edge(5,6).
gadget_edge(6,0).
gadget_edge(6,2).
gadget_edge(6,7).
gadget_edge(7,0).
gadget_edge(7,3).
gadget_edge(7,5).

special_edge(a;b;c;d;e).

forces(a,b).
forces(b,c).
forcesn(c,a).
nforces(a,d).
forces(d,e).
forces(e,a).

relates(A,B) :- forces(A,B).
relates(A,B) :- nforces(A,B).
relates(A,B) :- forcesn(A,B).

is_se_pair(se_pair(A,B)) :- relates(A,B).
vertex_name(v(V,P)) :- gadget_vertex(V), is_se_pair(P).

matches(from(A), v(5, se_pair(A,B))) :- forces(A,B).
matches(to(A), v(1, se_pair(A,B))) :- forces(A,B).
matches(from(B), v(3, se_pair(A,B))) :- forces(A,B).
matches(to(B), v(6, se_pair(A,B))) :- forces(A,B).

matches(from(A), v(2, se_pair(A,B))) :- nforces(A,B).
matches(to(A), v(7, se_pair(A,B))) :- nforces(A,B).
matches(from(B), v(1, se_pair(A,B))) :- nforces(A,B).
matches(to(B), v(3, se_pair(A,B))) :- nforces(A,B).

matches(from(A), v(7, se_pair(A,B))) :- forcesn(A,B).
matches(to(A), v(3, se_pair(A,B))) :- forcesn(A,B).
matches(from(B), v(5, se_pair(A,B))) :- forcesn(A,B).
matches(to(B), v(1, se_pair(A,B))) :- forcesn(A,B).

same_vertex(V, V) :- vertex_name(V).
same_vertex(M, N; N, M) :- matches(X, M), matches(X, N).

already_found(v(Y,N2)) :- vertex_name(v(X,N1)), same_vertex(v(X,N1),v(Y,N2)), N1 < N2.
vertex(V) :- vertex_name(V), not already_found(V).

named_gadget_edge(edge(v(X,SE),v(Y,SE))) :- gadget_edge(X,Y), is_se_pair(SE).
from_gadget_edge_named(edge(A, B), edge(C,D)) :- named_gadget_edge(edge(C,D)), same_vertex(A,C), same_vertex(B,D), vertex(A), vertex(B).
from_gadget_edge(edge(A,B)) :- from_gadget_edge_named(edge(A,B),edge(C,D)).
is_edge(E) :- from_gadget_edge(E).
is_edge(edge(A,B)) :- vertex(A), vertex(B), A < B, not from_gadget_edge(edge(B,A)).

vertex_count(VN) :- VN = #count{vertex(V) : vertex(V)}.
edge_count(EN) :- EN = #count{is_edge(E) : is_edge(E)}.

#show vertex_count/1.
#show edge_count/1.

bidirectional :- is_edge(edge(A,B)), is_edge(edge(B,A)).
phantom_vertex :- is_edge(edge(A,B)), not vertex(A).
phantom_vertex :- is_edge(edge(A,B)), not vertex(B).
incomplete :- vertex(A), vertex(B), not is_edge(edge(A,B)), not is_edge(edge(B,A)), A != B.

#show bidirectional/0.
#show phantom_vertex/0.
#show incomplete/0.

SWAG- Vermutung [etwas Besseres als nichts?]:

$G = (V,E)$$F \subseteq E$$G$$O(1)$

^{Anmerkungen: Abschuss Gegenbeispiele willkommen! bisher scheint keiner gegeben zu sein. noch besser wären einige Beobachtungen von Mustern von Kantenorientierungen, die sich auf bestimmte Graphenklassen beziehen. oder etwas mehr Motivation oder Einbindung in bestehende Literatur. angeboten im Stil von Beweisen und Widerlegungen (Lakatos) ... auch, da es so ein ungewöhnliches Problem zu sein scheint, das [noch?] nicht viel zu tun hat, schlagen Sie vor, es empirisch zu studieren ...}