Jak drogie może być zniszczenie wszystkich długich ścieżek w DAG?

Uważamy DAG (skierowane wykresy acykliczne) z jednym węzłem źródłowym jeden docelowego węzła ; dozwolone są równoległe krawędzie łączące tę samą parę wierzchołków. - cięcie jest zestaw krawędzi, których usunięcie usunięcie wszystkich - ścieżek dłuższe niż ; krótsze - szlaki, a także wydłużone „wewnętrzny” (te, które nie ścieżki pomiędzy i ), mogą przeżyć!$s$$t$k s t k s t s $k$$s$$t$$k$$s$$t$$s$$t$

Pytanie: Czy wystarczy usunąć co najwyżej około krawędzi z DAG, aby zniszczyć wszystkie ścieżki - dłuższe niż ? $1/k$$s$$t$$k$

To znaczy, jeśli oznacza całkowitą liczbę krawędzi w , to czy każdy DAG ma przecięcie o co najwyżej około krawędzi? Dwa przykłady:$e(G)$$G$$G$$k$$e(G)/k$

1. Jeśli wszystkie ścieżki - mają długość , to istnieje -cut z krawędziami . Odnosi bo wtedy nie musi być rozłącznych -cuts: wystarczy warstwa węzły w zależności od ich odległości od węzła źródłowego . $s$$t$$> k$$k$$\leq e(G)/k$$k$$k$$G$$s$
2. Jeśli jest z przechodnią turnieju (pełna DAG), a także -cut z \ równoważnik K \ Binom {n / k} {2} \ ok e (G) / k krawędzie istnieje: ustalić topologiczne zamawiania z węzły, podziel węzły na k kolejnych przedziałów długości n / k i usuń wszystkie krawędzie łączące węzły tego samego przedziału; zniszczy to wszystkie ścieżki s - t dłuższe niż k . G = T n k ≤ k ( n /$G=T_n$$k$$\leq k\binom{n/k}{2} \approx e(G)/k$k n / k s t $k$$n/k$$s$$t$$k$

Uwaga 1: Naiwny próba dać pozytywną odpowiedź (który również próbował jako pierwszy) byłoby spróbować pokazać, że każdy musi mieć DAG o rozłącznych -cuts. Niestety, przykład 2 pokazuje, że ta próba może się nie powieść: za pomocą dobrego argumentu David Eppstein pokazał, że dla około wykres nie może mieć więcej niż cztery rozłączne cięcia- ! k k k $k$ $k$$k$n Tn$\sqrt{n}$$T_n$ $k$

Uwaga 2: Ważne jest, aby cut musiał tylko zniszczyć wszystkie długie ścieżki - , a niekoniecznie wszystkie długie ścieżki. Mianowicie, istnieje ¹ DAG, w których każde „czyste” cięcie (unikając krawędzi padających na lub ) musi zawierać prawie wszystkie krawędzie. Tak więc moje pytanie brzmi: czy możliwość usunięcia krawędzi również za pomocą lub znacznie zmniejszyć rozmiar cięcia ? Najprawdopodobniej odpowiedź jest przecząca, ale jak dotąd nie mogłem znaleźć kontrprzykładu. k s t k s t s t $k$$s$$t$$k$$s$$t$$s$$t$$k$

Motywacja: Moje pytanie jest motywowane przez udowodnienie dolnych granic monotonicznych sieci przełączania i prostowania. Taka sieć to po prostu DAG, którego niektóre krawędzie są oznaczone testami „czy ?” (nie ma testów ). Rozmiar sieci jest liczba oznakowanych krawędziach. Wektor wejściowy jest akceptowany, jeśli istnieje ścieżka - której wszystkie testy są zgodne z tym wektorem. Markov udowodnił, że jeśli monotoniczna funkcja boolowska nie ma minterms krótszych niż i nie ma maxterms krótszych niż , to rozmiar x i = 1 x i = 0 s t f l w l ⋅ w k ⋅ w k w k 0 $x_i=1$$x_i=0$$s$$t$$f$$l$$w$$l\cdot w$jest konieczne. Pozytywna odpowiedź na moje pytanie sugerowałaby, że sieci wielkości około są konieczne, jeśli przynajmniej zmienne muszą być ustawione na , aby zniszczyć wszystkie mintermy dłuższe niż .$k\cdot w_k$$w_k$$0$$k$

¹ Konstrukcja jest podana w tym artykule. Weź pełne drzewo binarne głębokości . Usuń wszystkie krawędzie. Dla każdego wewnętrznego węzła narysuj krawędź do z każdego liścia lewego poddrzewa i krawędź od do każdego liścia prawego poddrzewa . Zatem co dwa liście są połączone ścieżką o długości w DAG. Sam DAG ma węzłów i edge, ale krawędzie muszą zostać usunięte, aby zniszczyć wszystkie ścieżki dłuższe niżT log n v v T v v T v T 2 ∼ n ∼ n log n Ω ( n log n ) $T$$\log n$$v$$v$$T_v$$v$$T_v$$T$$2$$\sim n$$\sim n\log n$$\Omega(n\log n)$$\sqrt{n}$.

[Odpowiedź własna; to jest skrócona wersja, stara znajduje się tutaj ]

Z Georgem Schnitgerem zdaliśmy sobie sprawę, że odpowiedź na moje pytanie jest zdecydowanie przecząca : istnieją DAG (nawet o stałym stopniu), w których każdy cut musi mieć stały ułamek wszystkich krawędzi, a nie tylko około ułamka, jak w moje pytanie. (Nieco słabszy wyniku czego frakcja może być konieczne, można uzyskać stosując o wiele prostszą konstrukcję, o którym mowa w przypisie powyżej. Szybkie zapisu się to tutaj ) k 1 / k 1 / log $k$$1/k$$1/\log k$

Mianowicie w artykule „O zmniejszeniu głębokości i kratach” Georg skonstruował sekwencję ukierunkowanych wykresów acyklicznych o stałym maksymalnym stopniu na węzłach o następującej właściwości:H n d n = m 2 $H_n$$d$$n=m2^m$

• Dla każdej stałej istnieje stała taka, że ​​jeśli jakikolwiek podzbiór co najwyżej węzłów zostanie usunięty z , pozostały wykres zawiera ścieżkę o długości co najmniej . 0 ≤ ϵ < 1 c > 0 c n H n 2 ϵ $0\leq \epsilon < 1$$c > 0$$cn$$H_n$$2^{\epsilon m}$

Weźmy teraz dwa nowe węzły i , i narysuj krawędź od do każdego węzła oraz krawędź od każdego węzła do . Powstały wykres nadal ma co najwyżej krawędzi.s t s H n H n t G n 2 n + d n = O ( n $s$$t$$s$$H_n$$H_n$$t$$G_n$$2n+dn=O(n)$

Dla każdej stałej istnieje stała taka, że ​​jeśli jakikolwiek podzbiór co najwyżej krawędzi zostanie usunięty z , pozostały wykres zawiera ścieżkę - z lub więcej krawędzi. 0 ≤ ϵ < 1 c ′ > 0 c ′ n G n s t 2 ϵ $0\leq \epsilon < 1$$c ' > 0$$c'n$$G_n$$s$$t$$2^{\epsilon m}$

Dowód: Zadzwoń węzły wewnętrznych węzłach . Usunąć podzbiór najwyżej krawędzi z , gdzie . Następnie usuń węzeł wewnętrzny, jeśli padł na usuniętą krawędź. Zauważ, że najwyżej węzły wewnętrzne są następnie usuwane. Nie usunięto żadnego z incydentów krawędziowych dla ocalonych węzłów. W szczególności, każdy zachowany węzeł wewnętrzny jest nadal połączony z obydwoma węzłami i . Przy powyższej właściwości musi pozostać ścieżka o długości$H_n$ $G_n$$c'n$$G_n$$c'=c/2$$2c'n=cn$$s$$t$$H_n$$2^{\epsilon m}$składający się wyłącznie z ocalałych węzłów wewnętrznych. Ponieważ przetrwały punkty końcowe każdej z tych ścieżek, każdy z nich można rozszerzyć na ścieżkę - w . CO BYŁO DO OKAZANIA$s$$t$$G_n$

Konsekwencja jest smutna: nie istnieje żaden analog lematu Markowa dla funkcji z wieloma krótkimi mintermami, mimo że zbiór długich mintermów ma pewną „skomplikowaną” strukturę: nie można wówczas udowodnić żadnych superliniowych dolnych granic wielkości sieci za pomocą ten argument „długość razy szerokość”.

PS Ten argument „długość razy szerokość” (gdy wszystkie ścieżki - są wystarczająco długie) był wcześniej używany przez Moore'a i Shannona (1956). Jedyną różnicą jest to, że nie pozwalają na rektyfikacje (nieoznakowane krawędzie). Tak więc jest to w rzeczywistości „argument Moore-Shannon-Markov”.$s$$t$