Biorąc pod uwagę ważony Dag, czy istnieje algorytm O (V + E), który zastępuje każdą wagę sumą wag przodka?

Problemem jest oczywiście podwójne liczenie. Jest to dość łatwe dla niektórych klas DAG = drzewo, a nawet drzewo szeregowo-równoległe. Jedynym algorytmem, który znalazłem, który działa na ogólnych DAG w rozsądnym czasie, jest przybliżony (dyfuzja streszczenia), ale zwiększenie jego precyzji jest wykładnicze pod względem liczby bitów (i potrzebuję dużo bitów).

Tło: to zadanie jest wykonywane (kilka razy z różnymi „wagami”) w ramach obliczeń prawdopodobieństwa w BBChop (http://github.com/ealdwulf/bbchop) program do znajdowania przerywanych błędów (tj. Bayesowska wersja „ git bisect ”). Wspomniany DAG jest zatem historią zmian. Oznacza to, że liczba krawędzi prawdopodobnie nie zbliży się do kwadratu liczby węzłów, prawdopodobnie będzie mniejsza niż k razy liczba węzłów dla niektórych małych k. Niestety nie znalazłem żadnych innych użytecznych właściwości DAG wersji. Miałem na przykład nadzieję, że największy trójpodłączony komponent wzrośnie tylko jako pierwiastek kwadratowy z liczby węzłów, ale niestety (przynajmniej w historii jądra Linuksa) rośnie liniowo.

ds.algorithms graph-theory directed-acyclic-graph Ealdwulf
źródło

Wyjaśnij: tylko węzły mają ciężary, a nie krawędzie?

Heinrich Apfelmus

Tak, tylko węzły.

Ealdwulf

To wydaje się być prawie duplikatem cstheory.stackexchange.com/questions/553/… ?

Jukka Suomela

wydaje się to bardziej ogólne, ponieważ przypisanie wag jednostkowych wszystkim wierzchołkom zmniejsza ten problem do problemu osiągalności.

Suresh Venkat

Wydaje się, że zbliżenie nie jest trudne w przypadku niektórych dodatkowych czynników polilogu ...

Sariel Har-Peled,

Odpowiedzi:

Zakładamy, że wagi wierzchołków mogą być dowolnymi dodatnimi liczbami całkowitymi, a dokładniej, mogą być dodatnimi liczbami całkowitymi co najwyżej 2 ⁿ . Wówczas bieżące zadanie nie może być wykonane nawet w nieco słabszym przedziale czasowym O ( n ² ), chyba że przechodnie przechodzenie dowolnego ukierunkowanego wykresu można obliczyć w czasie O ( n ² ), gdzie n oznacza liczbę wierzchołków. (Należy zauważyć, że algorytm czasowy O ( n ² ) dla zamknięcia przechodniego będzie przełomem.) Jest to przeciwieństwo następującego twierdzenia:

Roszczenie . Jeśli bieżące zadanie można wykonać w czasie O ( n ² ), przechodnie przechodzenie dowolnego ukierunkowanego wykresu podanego jako jego macierz przylegania można obliczyć w czasie O ( n ² ) (przy założeniu pewnego rozsądnego modelu obliczeniowego).

Dowód . W ramach przetwarzania wstępnego obliczamy silnie połączony rozkład składowy danego ukierunkowanego wykresu G w czasie O ( n ² ), aby otrzymać DAG G '. Zauważ, że jeśli możemy obliczyć przechodnie zamknięcie G ', możemy zrekonstruować przechodnie zamknięcie G' .

Teraz przypisz wagę 2 ⁱ do każdego wierzchołka i DAG G 'i użyj algorytmu dla bieżącego problemu. Następnie binarna reprezentacja sumy przypisanej do każdego wierzchołka i opisuje dokładnie zbiór przodków i , innymi słowy, obliczyliśmy przechodnie zamknięcie G '. QED .

Odwrotne jest również twierdzenie: jeśli możesz obliczyć przechodnie zamknięcie danego DAG, łatwo jest obliczyć wymagane sumy przez dodatkową pracę w czasie O ( n ² ). Dlatego teoretycznie można osiągnąć bieżące zadanie w czasie O ( n ^2.376 ), stosując algorytm do przechodzenia w oparciu o algorytm mnożenia macierzy Coppersmitha-Winograda .

Edycja : Wersja 2 i wcześniejsze nie zawierały wyraźnego założenia dotyczącego zakresu wag wierzchołków. Per Vognsen zauważył w komentarzu, że to domniemane założenie może nie być rozsądne (dzięki!) I zgadzam się. Nawet jeśli w aplikacjach nie są potrzebne arbitralne wagi, myślę, że ta odpowiedź może wykluczyć niektóre podejścia według następującego rozumowania: „Jeśli to podejście zadziałałoby, dałoby algorytm dla dowolnych wag, co jest wykluczone, chyba że przechodni zamknięcie można obliczyć w czasie O ( n ² ). ”

Edycja : Wersja 4 i wcześniejsze nieprawidłowo podały kierunek krawędzi.

Tsuyoshi Ito
źródło

Myślałem o tej rzeczy ostatniej nocy, ponieważ jedno praktyczne rozwiązanie wykorzystuje wektory bitowe do liczenia wykluczeń. Wydaje mi się, że jedynym pytaniem jest, czy rozsądnie jest założyć, że ciężary mogą mieć długość bitów proporcjonalną do n. W praktyce mogę sobie wyobrazić, że wagi są ograniczone przez pewne k, tak że maksymalna możliwa suma to kn, co nie wystarcza, aby wyciągnąć tę sztuczkę.

Per Vognsen

@Per: Zgadzam się, że założenie, że wagi wierzchołków mogą być liczbami całkowitymi n-bitowymi, może być wątpliwe. Zredagowałem odpowiedź, aby wyjaśnić to założenie. Dzięki!

Tsuyoshi Ito

@Per: Zrozumiałem, że jeśli wagi wierzchołków są liczbami całkowitymi ograniczonymi przez O (1), problem ogranicza się do przypadku, gdy wszystkie wierzchołki mają wagę 1 poprzez odpowiednie skopiowanie wierzchołków.

Tsuyoshi Ito

Niestety w tym wątku nie widzę odpowiedzi na problem z liczeniem. Liczby zawierają logarytmicznie mniej informacji niż lista zamknięcia przechodniego, O (n log n) vs O (n ^ 2), więc nie rozumiem, jak może działać prosta redukcja.

Per Vognsen

Nawiasem mówiąc, interesująca wersja tego problemu występuje, gdy mamy do czynienia z czynnikiem rozgałęzionym i informacją o wzroście wielkości pokoleń (rodzaj la topologiczny) DAG. Jeśli wzrost jest wykładniczy, wzór jest zasadniczo podobny do drzewa. Co jeśli jest liniowy, logarytmiczno-liniowy, kwadratowy itp.?

Per Vognsen

Jest to rozwinięcie mojego komentarza do odpowiedzi Tsuyoshi. Myślę, że negatywną odpowiedź na pytanie można uczynić bezwarunkową.

$\omega(n)$ $O(n)$

$G_{r,c}$ $r \times c$ $r$ $r$ $c$

$r = (\log\ n)/2$ $c = 2n/\log\ n$

$\sqrt{n}$ $\omega(\log\ n)$

$\omega(n)$ $2c(r-1) = O(n)$

Chodzi o to, że leżący u podstaw porządek częściowy jest gęsty, ale DAG reprezentuje redukcję przechodnią, która może być rzadka.

András Salamon
źródło

Ten argument jest interesujący, ale nie jestem pewien, czy można go przekształcić w dowód na jakiekolwiek interesujące stwierdzenie. Biorąc pod uwagę wszechobecną trudność udowodnienia dolnych granic problemów, ten argument wydaje mi się trudny.

Tsuyoshi Ito

@Tsuyoshi: Myślę, że istnienie powinno działać za pomocą argumentu probabilistycznego, a dolna granica jest słaba, więc wydaje się, że jest wystarczająco dużo miejsca do działania. Ale masz rację, jest to zręczne, że zdanie „średnio jednorazowe dodatki” potrzebuje lepszego fundamentu.

András Salamon

-2

To jest złe i opiera się na nieporozumieniu w kwestii. Dzięki Tsuyoshi za cierpliwe zwrócenie uwagi na mój błąd. Pozostawienie na wypadek, gdyby inni popełnili ten sam błąd.

$k$

$k$ $O(k|V|)$

$O(|V|+|E|)$

Takie podejście powinno również działać dobrze, jeśli istnieje kilka węzłów z wieloma bezpośrednimi poprzednikami, o ile są one stosunkowo rzadkie.

András Salamon
źródło

Nie rozumiem. Jak uniknąć podwójnego liczenia, gdy DAG nie jest drzewem? W rzeczywistości, jeśli się nie mylę, ogólny przypadek można sprowadzić do przypadku, w którym każdy wierzchołek ma co najwyżej dwóch poprzedników, a dowolny algorytm czasu liniowego dla drugiego przypadku daje algorytm czasu linii dla przypadku ogólnego.

Tsuyoshi Ito

O (| V | + | E |)

$O(|V|+|E|)$

k

$k$

Obawiam się, że źle zrozumiałeś mój komentarz. Kwestionuję poprawność twojego algorytmu, a nie czas działania. Załóżmy, że DAG z czterema wierzchołkami A, B, C, D z krawędziami A → B → D i A → C → D z każdym wierzchołkiem ma pewną wagę. Po obliczeniu sum częściowych dla B i C nie można po prostu dodać sum częściowych dla B i C, aby obliczyć sumę dla D, ponieważ spowodowałoby to dwukrotne dodanie wagi wierzchołka A.

Tsuyoshi Ito,

@Tsuyoshi: więc semantyka ma być „obliczeniowa

\sum_{u < v} w (u)

$\sum_{u < v} w(u)$

Tak. A teraz pamiętam, że kiedy zobaczyłem to pytanie po raz pierwszy, źle go odczytałem i pomyślałem, że będzie to oczywiste. Ale nie, prawdziwe pytanie jest trudniejsze. Czas pomyśleć….

Tsuyoshi Ito,