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

13

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

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ć?

G. Bach
źródło
1
perfekcyjnie, dzięki! (Usunąłem komentarz, ponieważ napisałem G = (E, V) zamiast standardowego G = (V, E) :-)
Marzio De Biasi
6
Jeśli dobrze rozumiem, jest to równoważne z pytaniem, czy przewagi w turnieju można podzielić na dwie grupy DAG, z których jedna jest przejściowo zamknięta.
dspyz
1
W komentarzu dspyz nie ma tylu problemów z DAG, które można badać ze względu na ich złożoność. wydaje się, że wcale nie jest tak wiele twierdzeń na temat DAG. drzewa są nieco bardziej dostępne. Twój problem (choć na pozór interesujący, co odzwierciedlają głosy) wydaje się mieszać ze sobą wiele niezwykłych elementów i nie mieści się w żadnej konkretnej kategorii.
vzn
5
@IgorShinkar łuki dowolnego digrafu można trywialnie podzielić na dwa DAG: uporządkuj wierzchołki dowolnie; jeden DAG to krawędzie przednie, drugi DAG to krawędzie wsteczne.
Sasho Nikolov
1
@SashoNikolov oczywiście!
Igor Shinkar

Odpowiedzi:

4

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:

wykres gadżetowy używany do wymuszania implikacji

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:

  • ¬(2,7)(1,3)
  • (5,1)(3,6)
  • (7,3)¬(5,1)

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

konstrukcja dla wykresu, który nie ma TFAS

A

G. Bach
źródło
Przepraszam, nie podążam. Czy jest jakiś powód, dla którego nie możesz po prostu opublikować listy krawędzi, abym mógł uruchomić ją przez solver ASP i spróbować go zweryfikować? Według clingo, twój wykres gadżetów ma 8 różnych TFAS. Oto najmniejszy: tfas (edge ​​(5,0)) tfas (edge ​​(6,0)) tfas (edge ​​(7,0)) tfas (edge ​​(6,2)) tfas (edge ​​(7,3)) tfas (edge ​​(1,2)) tfas (edge ​​(1,3)) tfas (edge ​​(7,5))
dspyz 30.01.2014
Właśnie zauważyłem, że wspomniałeś o krawędzi (6,3) na wykresie gadżetów, ale obraz, który podałeś, ma krawędź (3,6)
dspyz 30.01.2014
Zrozumiałem, zobacz moją zaktualizowaną odpowiedź: cstheory.stackexchange.com/a/20778/13643
dspyz
@dspyz Myślałem, że konstrukcja jest bardziej przejrzysta niż tylko lista krawędzi, ponieważ jeśli moje rozumowanie nie jest błędne, wszystko, co należałoby zweryfikować, to czy turniej nad konstrukcją rzeczywiście ma te implikacje. Dziękujemy za zwrócenie uwagi na błąd dotyczący krawędzi (3,6)! Mam również 8 TFAS dla tego gadżetu, ten, który wymieniłeś, jest jednym z nich.
G. Bach
Przykro mi. Źle skonstruowałem wykres. Naprawiłem to i clingo nie zgłasza teraz TFAS.
dspyz
1

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.
dspyz
źródło
Jestem pewien, że jest turniej na 18 wierzchołkach, który nie ma TFAS.
G. Bach
Czy możesz podać to jako przykład? Wystarczy załączyć plik z wymienionymi krawędziami
dspyz
Jak załączyć plik? Może to potrwać kilka godzin, nie mam teraz turnieju do rozdania. Również przeliczyłem się, powinien mieć 34 wierzchołki. Prawdopodobnie łatwiej jest zweryfikować, czy podam elementy składowe turnieju.
G. Bach
Prześlij na dowolny host pliku i link do niego (patrz meta.stackexchange.com/a/4643/185877 ) lub, jeśli ma on regularną strukturę, po prostu opisz go (podaj bloki konstrukcyjne)
dspyz
n
0

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

G=(V,E)FEGO(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 ...

vzn
źródło
1
Uruchomiłem program, aby sprawdzić, czy to się utrzymuje, i stwierdziłem, że istnieją turnieje, które nie mają ustawionego przejścia przechodni. Napiszę jutro jeden, nie będę się dziś do tego zabierał.
G. Bach
@vzn czy możesz udowodnić przypuszczenie o losowym turnieju?
Igor Shinkar
Kontrprzykład z tylko 5 wierzchołkami: a-> b, a-> c, b-> c, d-> a, b-> d, c-> d, e-> a, e-> b, c-> e , d-> e. Dla dowolnych czterech wierzchołków wykres indukowany zawiera cykl, więc przechodnie DAG może zawierać co najwyżej 3 krawędzie spośród 3 wierzchołków wykresu. Jest tylko 5 możliwości (wszystkie inne trojaczki są cyklami): abc, eab, dea, bcd, cde Łatwo jest sprawdzić, czy w każdym z pięciu przypadków jest cykl między pozostałymi 7 krawędziami
dspyz
1
Tak, nvr, nie jest to kontrprzykład
dspyz
1
@dspyz Sprawdziłem brutalnie wszystkie turnieje na maksymalnie 8 wierzchołkach. Wszystkie z nich mają przechodnie zestawy informacji zwrotnych, ale są takie, których możesz użyć do zbudowania turnieju, który tego nie robi.
G. Bach