Minimalny równoważny digraf w odniesieniu do źródeł i zlewów

Biorąc DAG (skierowane acykliczny wykres) ze źródła i zlewy . Znajdź DAG ze źródłami i pochłaniaczami , z minimalną liczbą krawędzi, tak aby: $D$ $S$ $T$ $D'$ $S$ $T$

Dla wszystkich par istnieje ścieżka od do w wtedy i tylko wtedy, gdy istnieje ścieżka od do w . $u \in S, v \in T$ $u$ $v$ $D$ $u$ $v$ $D'$

Jedna z tych aplikacji reprezentuje zestaw rodziny przez DAG. W przypadku takiej reprezentacji każde źródło jest zmienną we wszechświecie, a każdy ujście jest zbiorem w rodzinie zestawów, a element u znajduje się w zestawie S wtedy i tylko wtedy, gdy istnieje ścieżka od wierzchołka reprezentującego u do wierzchołka reprezentującego zestawy.

Czy ten problem jest dobrze znany? Czy istnieje algorytm wielomianowy dla tego problemu?

graph-theory graph-algorithms Martin Vatshelle
źródło

Myślę, że rozwiązaniem musi być podgrupa oryginalnego wykresu, prawda? Jeśli tak, myślę, że problem ten obejmuje Zestaw okładki, poprzez standardowe zmniejszenie, które pokazuje, że drzewo Sterowanego Steinera jest trudne: Utwórz wierzchołek dla każdego elementu, wierzchołek dla każdego zestawu i skierowaną krawędź (S, u), jeśli zestaw S zawiera element u. Następnie dodaj nowy wierzchołek i krawędzie do wszystkich ustawionych wierzchołków. Z tego nowego wierzchołka jest ścieżka do wszystkich ujść (wierzchołków elementu). Aby zachować je wszystkie, musimy wybrać minimalną liczbę zestawów wierzchołków obejmującą wszystkie elementy.

Michael Lampis,

Nie, ogólnie powiedziałbym, że nie powinien być subgrafem oryginalnego wykresu. Źródła są elementami i potrzebujesz elementu, jeśli tylko zestaw zawiera ten element. Zlewozmywaki są zestawami i nie można usunąć zestawów, które powinny reprezentować, więc jedyną rzeczą, jaką można zrobić, jeśli zaczniemy od naiwnego wykresu, na którym wszystkie węzły są zlewami lub źródłami, jest dodanie wierzchołków i przesunięcie / usunięcie krawędzi.

Martin Vatshelle,

Problem nie wydaje się jeszcze dobrze zdefiniowany. Jakie są ograniczenia dotyczące zestawu wierzchołków

? Czy potrzebujesz, aby zestaw wierzchołków

był taki sam jak zestaw wierzchołków

? Czy źródła i ujścia

są takie same jak źródła i ujścia

? Czy istnieje funkcja

odwzorowująca wierzchołek

na wierzchołek

, a warunkiem jest to, że istnieje ścieżka od

iff istnieje ścieżka od

D^{'}

$D'$

D^{'}

$D'$

D

$D$

D^{'}

$D'$

D

$D$

f : V_{D} \to V_{D^{'}}

$f:V_D \to V_{D'}$

D

$D$

D^{'}

$D'$

u

$u$

v

$v$

D

$D$

? Każdy może prowadzić do nieco innego problemu. Edytuj pytanie, aby wyjaśnić?

f (u)

$f(u)$

f (v)

$f(v)$

D^{'}

$D'$

Wyjaśniłem pytanie, w istocie mam na myśli to, że źródła i ujścia są takie same. Myślę, że mapowanie jest dość bliskie temu samemu, jedynym sposobem na mapowanie dwóch zlewów do tego samego węzła jest to, że są one osiągalne z tego samego zestawu źródeł, tj. Reprezentują ten sam zestaw. Jedynym sposobem, w jaki dwa źródła mogą być zmapowane do tego samego węzła, jest osiągnięcie dokładnie tych samych ujść. Myślę więc, że po prostym wstępnym przetworzeniu D problemy byłyby równoważne.

Martin Vatshelle,

Dag D w rzeczywistości nie ma znaczenia dla problemu, prawda? Równie dobrze możesz wziąć dwustronny wykres między S i T jako dane wejściowe.

Emil Jeřábek

Załóżmy, że zawiera tylko źródła i ujścia, ponieważ dane wejściowe można łatwo przetłumaczyć na równoważne dane wejściowe. $D$

Następnie należy zauważyć, że w każdym roztworze do , dla każdego wierzchołka odpowiada biclique w bazowych nieukierunkowane grafu z (The biclique pomiędzy wszystkich źródeł zasięg w i wszystkie zlewy, które są osiągane ze w ). $D'$ $D$ $v$ $G$ $D$ $v$ $D'$ $v$ $D'$

I przypuszczać, że jeśli jest optymalne, to zawiera on wierzchołek Cut, w stosunku 1: 1 odpowiada optymalnej biclique Pokrycie . Następnie, każdy wierzchołek minimalna cięcia w odpowiada biclique optymalnego pokrycia w . Ponieważ jednak BICLIQUE COVER (aka BIPARTITE DIMENSION) jest NP-zupełny, twój problem raczej nie zaakceptuje algorytmu czasu wielomianowego, chyba że moja hipoteza się nie powiedzie. $D'$ $G$ $D'$ $G$

Zauważ, że nawet jeśli moja hipoteza się utrzymuje, technicznie ten argument nie dowodzi twardości NP twojego problemu, ponieważ redukcja nie jest karpową, lecz redukcją Cooka.

igel
źródło

Minimalny równoważny digraf w odniesieniu do źródeł i zlewów

Odpowiedzi: