Zestaw łuków ze sprzężeniem zwrotnym (TFAS): NP-complete?

Jakiś czas temu wysłałem prośbę o referencję dotyczącą problemów z grafem, w której chcemy znaleźć 2-partycję krawędzi, w której oba zestawy spełniają właściwość niezwiązaną z ich licznością. Próbowałem udowodnić, że następujący problem jest NP-trudny:

Biorąc pod uwagę turniej , czy istnieje zestaw sprzężeń zwrotnych F ⊆ E w G, który definiuje relację przechodnią?$G = (V,E)$$F \subseteq E$$G$

Mam konstrukcję na próbę dowodu, ale wygląda na to, że wpadnie to w ślepy zaułek, więc pomyślałem, że mogę tutaj zapytać, czy coś mi brakuje. Aby nie ograniczać swojej kreatywności do kierunków myślenia podobnych do tych, z których korzystałem, nie zamieszczę tutaj mojej próby.

Czy ten problem jest trudny NP? Jeśli tak, jak to udowodnić?

Aby dodać mały kontekst, oto konstrukcja wykresu, który nie ma ustawionego łuku przechodniego sprzężenia zwrotnego. Do tej konstrukcji użyję następującego wykresu gadżetów:

Ten turniej ma następujące właściwości (które sprawdziłem za pomocą programu, nie udowodniłem tego formalnie):

• jeśli (2,7) nie ma w danym TFAS, to (1,3) jest
• jeśli (5,1) znajduje się w danym TFAS, to również (3,6)
• jeśli (7,3) jest w danym TFAS, to (5,1) nie

lub nieco nadużywając notacji logiki predykatu:

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

Zauważysz, że dla każdej implikacji dwie krawędzie są rozłączone parami, więc następujące prace budowlane:

$A$

Uruchomiłem krótki program clingo, który nie zgłosił żadnego wykresu bez TFAS, ale wystąpił błąd. Naprawiłem to i teraz sprawdza, czy nie ma wykresu bez TFAS dla n = 8 lub mniej. Dla n = 9 znajduje to:

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))

Oto (stałe) kodowanie

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

Uruchom go za clingo -c n=7 tfas.asppomocą (Korzystanie z clingo 4.2.1)

(n = 7 oznacza wykresy dokładnie 7 wierzchołków)

Powinien zwrócić zadowalający wtedy i tylko wtedy, gdy istnieje wykres bez TFAS na 7 wierzchołkach.

Ok, zorientowałem się, co opisuje wykres @ G.Bach, i zakodowałem go w clingo (patrz opis clingo poniżej. Zaczyna się od opisu wykresu gadżetów i przechodzi do opisu, jak połączyć kopie razem, aby uzyskać pełny Opis 34-wierzchołkowego turnieju G.Bach opisuje. Załączam również opis uziemionego grafu).

Następnie zacząłem uruchamiać clingo na tym wykresie i twierdziłem, że znalazłem TFAS z 241 krawędziami. Ale popełniłem błąd w kodowaniu wykresu. Naprawiłem błąd, a clingo zgłasza teraz niezadowolenie (tzn. Nie ma TFAS).

Oto program znajdowania TFAS na wykresie

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

Oto (zaktualizowany) program do generowania wykresu G.Bacha. Na końcu dodałem wskaźniki, aby sprawdzić, czy wykres jest dobrze uformowanym wykresem turniejowym:

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.

Przypuszczenie SWAG [coś lepszego niż nic?]:

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

^{uwagi: Witamy w kontrprzykładach! jak dotąd wydaje się, że nie podano żadnego. jeszcze lepsze byłyby niektóre obserwacje wzorów orientacji krawędzi związanych z poszczególnymi klasami grafów. lub trochę więcej motywacji lub powiązanie jej z istniejącą literaturą. oferowane w stylu dowodów i odrzuceń (Lakatos) ... również, ponieważ wydaje się tak niecodzienny problem, który [jeszcze?] nie odnosi się do wielu, sugeruje zbadanie go empirycznie ...}