Ile rozcięć krawędzi musi mieć DAG?

Następujące pytanie jest związane z optymalności Bellmana-Forda - najkrótsza droga algorytm programowania dynamicznego (patrz ten post dla połączenia). Pozytywna odpowiedź sugerowałaby również, że minimalny rozmiar monotonicznego niedeterministycznego programu do rozgałęziania dla problemu STCONN to . $s$$t$$\Theta(n^3)$

Niech być DAG (skierowane acykliczny wykres) z jednym węzłem źródłowym jeden docelowego węzła . - cięcie to zestaw krawędzi, których usunięcie usunięcie wszystkich - ścieżek długości ; zakładamy, że w są takie ścieżki . Zauważ, że krótsze ścieżki - nie muszą być niszczone.s t $G$$s$$t$$k$t ≥ k G s $s$$t$$\geq k$$G$$s$$t$

Pytanie: Czy musi mieć co najmniej (o) rozłącznych -cuts? $G$$k$ $k$

Jeśli nie ma ścieżek - krótszych niż , odpowiedź brzmi TAK, ponieważ mamy następujący znany fakt min-max (podwójny z twierdzenia Mengera ) przypisany Robacker . - cięcia jest -cut dla (niszczą wszystkie - ki).t $s$$t$$k$^$\ast$t k k = $s$$t$$k$$k=1$ $s$$t$

Fakt: Na dowolnym skierowanym wykresie maksymalna liczba cięć $s$ - rozłącznych od krawędzi $t$jest równa minimalnej długości ścieżki $s$ - $t$ .

Pamiętaj, że dotyczy to nawet sytuacji, gdy wykres nie jest acykliczny.

Dowód: Trywialnie, minimum to co najmniej maksimum, ponieważ każda ścieżka - t przecina każdą s - t wyciętą na krawędzi. Aby zobaczyć równość, niech d ( u ) będzie długością najkrótszej ścieżki od s do u . Niech U r = { u : d ( u ) = r } , dla r = 1 , … , d ( t ) , i niech E $s$$t$$s$$t$$d(u)$$s$$u$$U_r=\{u\colon d(u)=r\}$$r = 1,\ldots, d(t)$$E_r$być zbiorem krawędzi pozostawiających . Jest oczywiste, że zestawy e r są rozłączne, ponieważ zestawy U R są takie. Tak więc, pozostaje on, że każda z e r oznacza s - t cięcia. Aby to wykazać, brać dowolna s - t ścieżka p = ( U 1 , U 2 , ... , U m ) z u 1 = a a u m = T . Ponieważ $U_r$$E_r$$U_r$$E_r$$s$$t$$s$$t$$p=(u_1, u_2, \ldots,u_m)$$u_1=s$$u_m=t$ , sekwencja odległości d ( u 1 ) , … , d ( u m ) musi osiągnąć wartość d ( u m ) = d ( t ) , zaczynając od d ( u 1 ) = d ( s ) = 0 i zwiększenie wartości o maksymalnie$d(u_{i+1})\leq d(u_i)+1$$d(u_1),\ldots,d(u_m)$$d(u_m)=d(t)$$d(u_1)=d(s)=0$$1$na każdym kroku. Jeśli jakaś wartość zostanie zmniejszona, wówczas musimy osiągnąć wartość d ( u i ) później. Musi więc istnieć j, gdzie następuje skok z d ( u j ) = r do d ( u j + 1 ) = r + 1 , co oznacza, że ​​krawędź ( u j , u j + 1 ) należy do E r , ponieważ pożądany. CO BYŁO DO OKAZANIA $d(u_i)$$d(u_i)$$j$$d(u_j)=r$$d(u_{j+1})=r+1$$(u_j,u_{j+1})$$E_r$

Ale co, jeśli istnieją również krótsze (niż ) ścieżki? Wszelkie wskazówki / referencje? $k$

---

JT Robacker, twierdzenia Min-Max o najkrótszych łańcuchach i rozłącznych odcinkach sieci, Memorandum badawcze RM-1660, The RAND Corporation, Santa Monica, Kalifornia, [12 stycznia] 1956 r. $^{\ast}$

---

EDIT (dzień później): Przez krótki i bardzo miły argumentem, David Eppstein odpowiedział na pytanie powyżej w oryginalny negatyw : im kompletny DAG (a przechodni turnieju ) nie może mieć więcej niż cztery rozłączne k -cuts! W rzeczywistości dowodzi on następującego interesującego faktu strukturalnego , dla k około $T_n$$k$$k$ . Cięcie jestczyste,jeśli nie zawiera krawędzi padających naslubt.$\sqrt{n}$$s$$t$

Każdy czysty cut w T n zawiera ścieżkę o długości k . $k$$T_n$$k$

Oznacza to w szczególności, że co dwa czyste cięcia muszą się przecinać! Ale być może wciąż istnieje wiele czystych cięć typu K , które nie nakładają się na „za dużo”. Stąd łagodne pytanie (konsekwencje dla STCONN byłyby takie same ):$k$$k$

Pytanie 2: Jeśli każdy czysty cut ma ≥ M krawędzi, to czy wykres musi mieć około Ω ( k ⋅ M ) krawędzi? $k$$\geq M$$\Omega(k\cdot M)$

Połączenie ze złożonością STCONN pochodzi od związku z Erdös i Gallai które trzeba usunąć wszystkie ale krawędzie od (niekierowanego) K m , aby zniszczyć wszystkie ścieżki o długości k . $(k-1)m/2$$K_m$$k$

---

EDYCJA 2: Zadałem teraz pytanie 2 w Mathoverflow .

Krótka odpowiedź: nie.

Niech być kompletny DAG (przechodni turnieju) w n wierzchołków z s i t źródło i umywalki, niech k = $G$$n$$s$$t$ . Zauważ, że mogą występować co najwyżej cztery rozłączne nacięcia, które zawierają więcej niżn/3krawędziprzypadających naslub więcej niżn/3krawędzi przypadających nat. Jeśli więc ma być wiele rozłącznych cięć, możemy założyć, że istnieje cięcieC,które nie zawiera dużej liczby krawędzi przypadających nasit.$k=\sqrt{n/3}$$n/3$$s$$n/3$$t$$C$$s$$t$

Teraz jest pełna subgraph indukowane w G przez zbiór wierzchołków x tak, że krawędzie s x i x t , nie należą do C . Liczba wierzchołków w X wynosi co najmniej n / 3 , ponieważ w przeciwnym razie C dotknie zbyt wielu krawędzi padających na s lub t . Jednak X ∖ C nie może zawierać ścieżki- k , ponieważ jeśli taka ścieżka istniała, można ją połączyć za pomocą s i t, tworząc długą ścieżkę w $X$$G$$x$$sx$$xt$$C$$X$$n/3$$C$$s$$t$$X\setminus C$$k$$s$$t$ . Dlatego najdłuższe warstwowanie X ∖ C ma mniej niż k warstw i ma warstwę zawierającą więcej niż ( n / 3 ) / k = k wierzchołków. Ponieważ jest to warstwa najdłuższego warstwowania ścieżki, jest ona niezależna w X ∖ C , a zatem kompletna w C , więc C zawiera ścieżkę P przez wierzchołki tej warstwy o długości k . Ta ścieżka musi być niezależna od wszystkich innych cięć.$G\setminus C$$X\setminus C$$k$$(n/3)/k=k$$X\setminus C$$C$$C$$P$$k$

Każde cięcie, które nie jest musi zawierać albo krawędź od s do początku ścieżki P, albo krawędź od końca ścieżki P do t , w przeciwnym razie nie blokuje ścieżki s - P - t . Więc jeśli C istnieje, mogą istnieć maksymalnie trzy rozłączne cięcia. A jeśli C nie istnieje (to znaczy, jeśli wszystkie cięcia obejmują więcej niż n / 3 krawędzi przypadających na s lub t ), mogą występować co najwyżej cztery rozłączne cięcia. Tak czy inaczej, jest to o wiele mniej niż k cięć.$C$$s$$P$$P$$t$$s$$P$$t$$C$$C$$n/3$$s$$t$$k$