Przejściowa redukcja DAG

13

Szukam algorytmu O (V + E) do znajdowania redukcji przechodnich przy danym DAG.

To oznacza usunięcie jak największej liczby krawędzi, abyś mógł dosięgnąć v od ciebie, dla dowolnych v iu nadal możesz sięgnąć po usunięciu krawędzi.

Jeśli jest to standardowy problem, proszę wskazać mi jakieś rozwiązanie modelowe.

algorithms graphs dag Karan
źródło

Nie możesz użyć odnośnika podanego w cytacie z wikipedii?

Hendrik Jan

2

Cóż, algorytm omawiany w Wikipedii działa w

(w najlepszym przypadku, tj. W przypadku wykresów acyklicznych) zamiast

zgodnie z żądaniem. Myślę, że właściwą odpowiedzią jest to, że algorytm, którego obecnie szukasz, może nie istnieć

O (V \times E)

$O(V\times E)$

O (V + E)

$O(V+E)$

Carlos Linares López

1

Zgodziliśmy się, że nie jest jasne, że to, o co prosisz, istnieje. Istnieje wiele prac, które nie byłyby interesujące, gdyby istniał taki algorytm, na przykład sciencedirect.com/science/article/pii/0012365X9390164O . To powiedziawszy, jeśli możesz sprecyzować swoją motywację, mogą istnieć bardziej konkretne rozwiązania. Na przykład, czy wiesz coś jeszcze na temat wykresu lub czy

zadziała?

O (n (n + m))

$O(n(n+m))$

William Macrae,

Gdzieś widziałem problem, ale nie było żadnych dodatkowych informacji, może literówka w tym problemie.

Karan

1

Co jeśli nie topologiczną rodzaju w DAG, ale śledzić osiągalnych wierzchołków za pomocą dzieciom, czyli

r e a c h a b l e [v] = \cup_{v^{'} \in c h i l d r e n_{v}} r e a c h a b l e [v^{'}]

$reachable[v] = \cup_{v' \in children_v} reachable[v']$ , następnie zacznij od najnowszego elementu na posortowanym wykresie i usuń nieużywane krawędzie i przejdź w górę, zachowując osiągalną funkcję, daje to maksymalne możliwe krawędzie do usunięcia, ale nie jestem pewien, czy otrzyma maksymalną możliwość (to

.

O (| E | + | V |)

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

8

Możemy rozwiązać ten problem po prostu wykonując DFS z każdego wierzchołka.

Dla każdego wierzchołka uruchom DFS od każdego wierzchołka taki sposób, że jest bezpośrednim potomkiem , tj. to krawędź. $u \in G$ $v$ $v$ $u$ $(u,v)$
Dla każdego wierzchołka osiągalnego przez DFS z , usuń krawędź . $v'$ $v$ $(u, v')$

Ogólna złożoność powyższego jest złożonością działania DFS ', czyli . $N$ $O(N(N+M))$

pratyaksh
źródło

1

Zauważ, że asymptotycznie ma to tę samą złożoność co algorytm

w artykule na Wikipedii, do którego link znajduje się w samym pytaniu.

O (N M)

$O(NM)$

David Richerby

1

Zgoda. Ponieważ należało udzielić zwięzłej odpowiedzi na to pytanie, przedstawiłem jedną. Ponadto, rozwiązanie

jest IMO, mało prawdopodobne.

O (N)

$O(N)$

pratyaksh

3

$O(|E|)$

$u$ $v$
$u$ $(v,u)$
$w$ $u$ $v$ $(v,w)$
$(v,v')$ $v'$ $v$

$v$ $(v',v)$ $v$

$O(|E|)$

AJed
źródło

1

Lemat: Jeśli istnieje krawędź V -> Y, a Y jest także pośrednim następcą V, (np. V -> W -> + Y), to krawędź V -> Y jest przechodnia i nie jest częścią pierwiastka przechodniego.

Metoda: Śledź przechodnie zamknięcie każdego wierzchołka, pracując od wierzchołka do początkowych wierzchołków w odwrotnej kolejności topologicznej. Zbiór pośrednich następców V jest związkiem przejściowych zamknięć bezpośrednich następców V. Przejściowe zamknięcie V jest związkiem jego pośrednich następców i bezpośrednich następców.

Algorytm:

    Initialise Visited as the empty set.
    For each vertex V of G, 
        Invoke Visit(V).

    Visit(V):
        If V is not in Visited,
            Add V to Visited, 
            Initialise Indirect as the empty set,
            For each edge V -> W in G,
                Invoke Visit(W),
                Add Closure(W) to Indirect.
            Set Closure(V) to Indirect.
            For each edge V -> W in G,
                Add W to Closure(V),
                If W is in the set Indirect,
                    Delete the edge V -> W from G.

Zakłada się, że masz jakiś skuteczny sposób śledzenia zestawów wierzchołków (np. Map bitowych), ale myślę, że to założenie zostało przyjęte również w innych algorytmach O (V + E).

Potencjalnie użytecznym efektem ubocznym jest znalezienie przechodniego zamknięcia każdego wierzchołka G.

DrBD
źródło

Usunąłem odpowiedź opublikowaną na twoim wcześniejszym koncie. Jeśli nadal chcesz połączyć swoje dwa konta, wykonaj czynności opisane w Centrum pomocy . Biorąc to pod uwagę, ponieważ wcześniejsze konto nie ma już żadnej widocznej treści, możesz po prostu trzymać się nowego.

Gilles 'SO - przestań być zły'

0

Rozwiązałem ten sam problem, ale nie był dokładnie taki sam. Poprosiłem o minimalną liczbę krawędzi na wykresie po zmniejszeniu, tak że pierwotnie połączone wierzchołki są nadal połączone i nie są tworzone nowe połączenia. Jak jest jasne, nie mówi się o znalezieniu zredukowanego wykresu, ale o tym, ile jest zbędnych krawędzi. Ten problem można rozwiązać w O (V + E). Link do wyjaśnienia to https://codeforces.com/blog/entry/56326 . Ale myślę, że tak naprawdę wykres będzie miał wysoką złożoność niż O (N)

Kumar Mohit
źródło

Przejściowa redukcja DAG

Odpowiedzi: