Czy znana jest złożoność tego problemu ścieżki?

Instancja: Niekierowany wykres $G$ z dwoma wyróżnionymi wierzchołkami i liczbą całkowitą . $s\neq t$ $k\geq 0$

Pytanie: Czy istnieje ścieżka w , taka, że przecina ona co najwyżej trójkątów? (W przypadku tego problemu mówi się, że ścieżka przecina trójkąt, jeśli ścieżka zawiera co najmniej jedną krawędź od trójkąta). $s-t$ $G$ $k$

cc.complexity-theory graph-algorithms Andras Farago
źródło

Czy to źle? Przypisujemy wagę do każdej krawędzi, a następnie znajdujemy najkrótszą drogę st. Ciężar każdej krawędzi to liczba trójkątów, które obejmują tę krawędź. Ciężar tej ścieżki nie jest równy liczbie napotkanych trójkątów, ale jest to ścieżka st z minimalną liczbą trójkątów. (Możliwym problemem jest to, że możemy policzyć jeden lub więcej trójkątów dwa razy, ponieważ odwiedzamy dwie krawędzie tego trójkąta, ale powodem ich wyboru jest to, że są one mniejsze niż przechodzenie przez drugą krawędź trójkąta, a także mamy proste ścieżki dwie krawędzie trójkąta znajdują się obok siebie).

Saeed

@ Tak, nie rozumiem: jaki jest argument, że przeliczanie nie powoduje wybrania ścieżki nieoptymalnej? Twój algorytm jest z pewnością przybliżeniem 2. Może poprawką jest dodanie krawędzi

(u, w)

$(u, w)$ dla każdej ścieżki

u \to v \to w

$u\to v \to w$ o wadze równej liczbie trójkątów zawierających oba

(u, v)

$(u,v)$ i

(v, w)

$(v,w)$

Sasho Nikolov

Racja, możemy przejść od u do v, a następnie wybieramy x (jakiś inny węzeł nie w trójkącie uvw), a następnie przechodzimy do w, co jest złe (mój błąd polegał na tym, że przeoczyłem między wierzchołkami, które nie są w trójkącie uvw) , ale poprawka jest poprawna, ponieważ dla każdej ścieżki z

α

$\alpha$ trójkąty na oryginalnym wykresie to ścieżka ciężaru

α

$\alpha$ na wykresie pomocniczym. Ponadto ciężar ścieżki na nowym wykresie jest zawsze co najmniej równy liczbie trójkątów na odpowiedniej ścieżce na oryginalnym wykresie.

Saeed,

Zastanawiam się nad tym, nawet jeśli po naprawie nie działa. Przepraszam Andras, jeśli przyniosłem złą nadzieję. Aby zobaczyć, dlaczego poprawka jest zła, rozważ wierzchołki

u - > v - > w - > x

$u->v->w->x$ na ścieżce

P

$P$ i mamy trójkąt

u, v, w

$u,v,w$ i

v, w, x

$v,w,x$ i załóżmy krawędzie

v x

$vx$ i

u w

$uw$ są przyczyną zbyt wielu trójkątów. Jeśli użyjemy nowej sztucznej krawędzi, która się łączy

u - > w

$u->w$ następnie policzyliśmy trójkąt

v, w, x

$v,w,x$ dwa razy. PS: Moje rozumowanie znów było błędne, ponieważ myślałem, że po prostu zastąpimy

u - > v

$u->v$ i

v - > w

$v->w$ z nową (wieloma) krawędziami

u - > w

$u->w$ . Jeśli dodamy te sztuczne krawędzie dla każdej ścieżki, zadziała to trywialnie. Wygląda na to, że jest to NPC.

Saeed

Mój pomysł nie zadziała - musiałbym utrzymać wiele zestawów i myślę, że będzie ich zbyt wiele.

reinierpost

Załóżmy, że nie ma żadnych krawędzi wewnętrznych $G$ .

Dla każdej krawędzi między węzłem $v_i$ i $v_j$ w $G$ , pozwolić $E[i,j]=1$ , i $E[i,j]=0$ jeśli nie ma krawędzi. Obliczać $n\times n$ matryca $C[i,j]=\sum_{k=1}^n E[i,k]\cdot E[k,j]$ , która podaje liczbę ścieżek dwóch przeskoków między każdą parą węzłów $v_i$ i $v_j$ . Następnie dla przewagi między $v_i$ i $v_j$ w $G$ obliczać $D[i,j]=E[i,j]\cdot C[i,j]$ inaczej ustawione $D[i,j]=\infty$ , co daje liczbę trójkątów, których część stanowi krawędź (lub nieskończoność, jeśli nie ma krawędzi). Mnożenie macierzy potrzebne do obliczeń $C$ koszty $O(n^3)$ (można go obliczyć szybciej w zależności od rzadkości $G$ ).

Teraz oblicz $n\times n$ matryca $A$ , takie że $A[i,j]=\min(D[i,j],\min_k(D[i,k]+D[k,j]-E[i,j]))$ . $A$ są wszystkie najkrótsze ścieżki w $D$ o długości do dwóch powiększonych w celu uwzględnienia ścieżek, które biegną wzdłuż dwóch krawędzi jakiegoś trójkąta.

Teraz wystarczy obliczyć najkrótszą ścieżkę pomiędzy $v_i$ i $v_j$ w $G$ na nowym wykresie $A$ jest (ważoną) macierzą przylegania za pomocą Dijkstry (ponieważ wszystkie masy krawędzi są dodatnie) tj. i określa, czy $A^*[i,j]\leq k$ , gdzie $A^*$ jest zamknięciem tropikalnego semiringu (co daje macierz odległości).

Edgar
źródło

Czy znana jest złożoność tego problemu ścieżki?

Odpowiedzi: