Znajdowanie co najmniej dwóch ścieżek o tej samej długości na ukierunkowanym wykresie

Załóżmy, że mamy skierowany wykres i dwa węzły i . Chciałbym wiedzieć, czy istnieją już algorytmy do obliczania następującego problemu decyzyjnego: $G=(V,E)$ $A$ $B$

Czy istnieją co najmniej dwie ścieżki między i o tej samej długości? $A$ $B$

Co powiesz na złożoność? Czy mogę to rozwiązać w czasie wielomianowym?

Chciałbym dodać nowe ograniczenie na wykresie, być może problem jest bardziej rozwiązywalny. W macierzy przylegania każda kolumna nie jest pusta. Tak więc każdy węzeł ma co najmniej jedną strzałkę na wejściu, a także co najmniej jeden węzeł jest podłączony do siebie. Więc jeśli węzeł jest węzłem, to jest krawędzią na wykresie. $i$ $(i,i)$

— Paolo Parisen T.
źródło

Miałeś na myśli proste ścieżki? (odwiedzając każdy węzeł najwyżej jeden raz). Czy mogą mieć także wspólny węzeł wewnętrzny?

nie, nie ma ograniczeń na ścieżkach. możesz zapętlić, jeśli chcesz.

— Paolo Parisen T.

Łatwa obserwacja jest taka: jeśli istnieje tylko jedna prosta ścieżka pomiędzy

, a to prosta droga jest podłączony do co najwyżej jednej pętli, można po prostu powiedzieć

, w przypadku wystąpienia co najmniej dwie pętle o różnej długości podłączone do tej prostej ścieżka, możesz powiedzieć tak, .... (Myślę, że podobne rzeczy są przydatne i możesz to udowodnić), ale w przypadku rozłącznych prostych ścieżek (jeśli podczas udowodnienia tego napotkałeś rozłączne proste ścieżki), jest to NPC.

A, B

$A,B$

N o

$No$

@mrm: Nie widzę tego jako duplikatu. Pytanie o wszystkie spacery to bardzo czasochłonna operacja (generalnie istnieje nieskończona liczba spacerów), podczas gdy OP żąda dwóch (prostych) ścieżek, nie wszystkich spacerów.

— Dave Clarke

Odpowiedzi:

Rozważmy wykres , chcemy wiedzieć, czy istnieją dwie różne ścieżki od do o tej samej długości. Co robić? Proste: koduj dwie ścieżki w jednym. Zdefiniuj wykres z wierzchołkami . Zrobić krok w tworząc dwa niezależne kroki w . Dodatkowy bit informuje, czy dwie ścieżki już się od siebie oddzieliły. $G$ $A$ $B$ $G'$ $V \times V \times \{0,1\}$ $G'$ $G$

Formalnie istnieje krawędź w iff , w i . $(i,j,e) \to (i',j',e')$ $G'$ $i \to i'$ $j \to j'$ $G$ $e'=e ∨ (i,i')≠(j,j')$

Algorytm sprawdza, czy istnieje ścieżka do w , czyli , czy coś w rodzaju . $(A,A,0)$ $(B,B,1)$ $G'$ $O(V^4)$ $O((V+E)^2)$

Jeśli zgodzisz się, że ten algorytm jest poprawny, to w konsekwencji ścieżka w ma długość co najwyżej , dlatego potencjalne „kolizje ścieżki” muszą wystąpić najpóźniej na tej długości. Z tej obserwacji można uzyskać algorytm , gdzie jest złożonością mnożenia macierzy (zapytaj, czy potrzebujesz spoilera ...). $G'$ $2n^2$ $O(V^{\omega} \log V)$ $\omega$

Mocno czuję, że istnieje algorytm , który wykorzystuje więcej struktury problemu. $O(V+E)$

— sdcvvc
źródło

To jest eleganckie.

— Raphael

Prawdopodobnie mam odpowiedź na ten problem, ale nie jestem pewien, czy to działa.

Nie jest ważne, aby „znaleźć” dwie ścieżki, jedyną ważną rzeczą jest „wiedzieć”, czy istnieją, czy nie. Nie sądzę, że jest to NP całkowity problem.

Więc, weź macierz sąsiedztwa . Możemy łatwo założyć, że jest wypełniony wartością 0,1. (0 = brak krawędzi; 1 = istnieje krawędź) Użyjmy następującej algebry z 3 wartościami (0,1,2), gdzie wszystko działa jak zwykle oprócz: ; $\textbf A$ $2+\text{<something>} = 2$ $2*\text{<whatever greater than 0>} = 2$

Tak więc, jeśli istnieją dwie ścieżki o tej samej długości od oczekuję, że istnieje wartość taka, że . $i,j$ $p$ $(\textbf A^p)_{i,j} = 2$

Niech jest liczbą wierzchołków na wykresie (lub, powiedzmy, że ma wymiar ). Nie znam wartości , ale jeśli iteruję , mnożąc się przez co najwyżej powinienem znaleźć odpowiedź. (więc ) (sens polega na tym, że sprawdzam , następnie sprawdzam , następnie sprawdzam i tak dalej ...) $n$ $\textbf A$ $n\times n$ $p$ $\textbf A$ $n^2$ $p<n^2$ $\text A$ $\text A^2$ $\text A^3$

oto moja argumentacja:

jeśli dwie ścieżki są ścieżkami prostymi, to działa; jeśli są, co najwyżej muszę iterować razy. $n$
Jeśli jest co najmniej jeden cykl zerowania lub jest ścieżka z dwoma cyklami, cóż, muszę znaleźć najmniejszą wspólną wielokrotność (LCM). jest z pewnością większą wartością i w mniej niż razy, jeśli istnieje, powinienem je znaleźć. $n^2$ $n^2$
Jeśli dwie ścieżki są dwiema różnymi ścieżkami, obie z jednym cyklem, to jest mniej więcej podobne do znalezienia rozwiązania dla tych dwóch równań: , gdzie i są długością tych dwóch różnych cykle Mnożenie macierzy , jak zdefiniowano powyżej, mówi „czy istnieje ścieżka od do której długość wynosi ?” Tak więc, jeśli jest większe niż , oznacza to, że istnieje więcej ścieżek prowadzących od do . Poprzez iterację macierzy $\alpha + \beta m = \gamma + \delta k$ $m$ $k$ $\text A^q$ $i$ $j$ $q$ $\textbf A^q$ $1$ $i$ $j$ razy przechodzimy przez wszystkie możliwe kombinacje i . Rzeczywiście, jest zdefiniowane jako i żaden cykl nie może być większy niż . $n^2$ $\delta$ $\beta$ $LCM(a,b)$ $(a*b)/GCD(a,b)$ $n$

Zatrzymuję się na iteracji, gdy znalazłem . $(\textbf A^p)_{i,j} = 2$

czy się mylę?

— Paolo Parisen T.
źródło

Próbowałem tego samego i napotkałem pewne problemy / niepewności: 1) Co zrobić, jeśli ścieżki są połączone z więcej niż jednym cyklem? Czy musisz „sprawdzać” wszystkie kombinacje (w najgorszym przypadku każdy węzeł ma wykładniczo wiele cykli!), Wysadzając górną granicę, czy też wystarczy rozważyć tylko jeden dla każdego? 2) Czy ze względu na stałe przesunięcia

LCM jest naprawdę górną granicą?

α

$\alpha$

γ

$\gamma$

— Raphael

Nawiasem mówiąc, nie ma potrzeby funky algebry: wystarczy zatrzymać moment, w którym obliczasz

jako wejście do macierzy.

2

$2$

— Raphael

n^{2}

$n^2$

n

$n$

α

$\alpha$

γ

$\gamma$

L C M (a, b) + α + γ < a * b + α + γ

$LCM(a,b) + \alpha+\gamma < a*b+\alpha + \gamma$

α + γ + a + b < n

$\alpha+\gamma+a+b < n$

a * b + α + γ

$a*b+\alpha+\gamma$

n^{2}

$n^2$