Kiedy wykres przyjmuje orientację, w której występuje co najwyżej jeden spacer?

Rozważ następujący problem:

Dane wejściowe: prosty (niekierowany) wykres $G=(V,E)$.

Pytanie: Czy istnieje orientacja spełniająca właściwość, że dla każdego istnieje co najwyżej jeden (skierowany) - spacer?$G$$s,t \in V$$s$$t$

Może to być równoważnie sformułowane jako:

Dane wejściowe: prosty (niekierowany) wykres .$G=(V,E)$

Pytanie: Czy istnieje acykliczna orientacja spełniająca właściwość, że dla każdego istnieje co najwyżej jedna (skierowana) ścieżka - ?$G$$s,t \in V$$s$$t$

Jaka jest klasa wykresów, dla której odpowiedź brzmi „tak”? Czy ten problem można rozwiązać w czasie wielomianowym?

Niektóre spostrzeżenia:

1. Jeśli wykres jest dwustronny, odpowiedź brzmi „tak”.
2. Jeśli wykres ma trójkąt, odpowiedź brzmi „nie”.

Pierwsza obserwacja następuje po zorientowaniu krawędzi od jednej przegrody do drugiej. Drugą obserwację łatwo sprawdzić. Doprowadziło mnie to do dwóch błędnych domysłów:

1. Odpowiedź brzmi „tak” wtedy i tylko wtedy, gdy wykres jest dwustronny. (kontrprzykład: 5-cyklowy)
2. Odpowiedź brzmi „tak” wtedy i tylko wtedy, gdy wykres nie zawiera trójkątów (kontrprzykład: iloczyn kartezjański krawędzi z 5 cyklami)

Jest NP-zupełny poprzez redukcję z nie do wszystkich równych 3SAT. Aby to zobaczyć, obserwuj to

• Jedyna poprawna orientacja a $4$-cykl to taki, w którym krawędzie zmieniają orientacje.
• Pozwolić $P$ być trójstronną nieukierunkowaną ścieżką i dodać wierzchołek stopnia drugiego przylegający do punktów końcowych $P$ utworzyć $5$-cykl. Wtedy jedyne orientacje$P$ które można rozszerzyć na prawidłowe orientacje całości $5$-cykl są tymi, w których $P$ nie jest konsekwentnie zorientowany jako ścieżka ukierunkowana.

Tworzymy zmienny gadżet dla zmiennej $v$ który należy do $k$ różne klauzule instancji NAE-3SAT poprzez sklejenie razem $k$ udostępnione $4$- motocykle na wspólnej krawędzi. Następnie w każdym z$4$- motocykle, krawędź przeciwna do krawędzi wspólnej musi być zorientowana spójnie ze wszystkimi pozostałymi $4$motocykle. Powiążemy wartość prawdy zmiennej z tą konsekwentną orientacją tych krawędzi. Dodatkowo, w dowolnej prawidłowej orientacji każdego z nich$4$- motocykle, nie ma drogi od jednego $4$-cykl na inny $4$-cykl, więc te gadżety mogą wchodzić w interakcje tylko w orientacji ich krawędzi, a nie poprzez istnienie dłuższych ścieżek.

Tworzymy gadżet klauzulowy dla klauzuli 3-zmiennej instancji NAE-3SAT poprzez sklejenie trzech $4$-cykluje krawędzie, naprzeciwko wspólnych krawędzi odpowiednich trzech zmiennych gadżetów, na ścieżkę 3-krawędziową $P$ a następnie dodanie wierzchołka drugiego stopnia do ukończenia $P$ w $5$-cykl. Jak omówiono powyżej, to$5$-cykl może być konsekwentnie zorientowany wtedy i tylko wtedy, gdy jego trzy krawędzie nie są zorientowane jako ścieżka ukierunkowana, co (przy prawidłowym sklejeniu) jest prawdziwe tylko wtedy, gdy wszystkie wartości prawdy związane z tymi orientacjami nie są równe.

Nawiasem mówiąc, DAGS z najwyżej jednym $s$-$t$ chodzić dla każdego $s$-$t$para była wcześniej badana jako „multitrees”, „silnie jednoznaczne wykresy” lub „namorzyny”; patrz https://en.wikipedia.org/wiki/Multitree