Minimalny rozcięcie na ważonych ukierunkowanych wykresach acyklicznych z potencjalnie ujemnymi wagami

Wystąpił następujący problem:

Biorąc pod uwagę ukierunkowany wykres acykliczny z rzeczywistymi wartościami grubości krawędzi oraz dwoma wierzchołkami s i t, oblicz minimalny st st cut.

Dla ogólnych wykresów jest to trudne NP, ponieważ można w prosty sposób zredukować maksymalne cięcie, po prostu odwracając wagi krawędzi (popraw mnie, jeśli się mylę).

Jaka jest sytuacja z DAG? Czy cięcie minimalne (lub maksymalne) można rozwiązać w czasie wielomianowym? Czy jest to trudne dla NP, a jeśli tak, to czy są znane algorytmy aproksymacyjne?

Próbowałem znaleźć pracę nad tym, ale nie byłem w stanie (może po prostu używam niewłaściwych słów kluczowych podczas wyszukiwania), więc miałem nadzieję, że ktoś może coś o tym wiedzieć (lub znaleźć).

algorithms complexity-theory graph-theory weighted-graphs Jerzy
źródło

Gdzie zawodzi sformułowanie programowania cięcia liniowego w programowaniu liniowym?

Peter Shor,

(używając notacji z en.wikipedia.org/wiki/… ): W przypadku krawędzi o ujemnej wadze d_ {ij} może być dowolnie duży. Nawet jeśli przeskoczysz d_ {ij} z góry, zawsze przyjmie maksymalną możliwą wartość dla krawędzi z ujemnymi ciężarami. Tak więc rozwiązanie takiego programu nie zawsze da prawidłowe cięcie. Mogę się mylić, ponieważ nie mam zbyt dużego doświadczenia z takimi problemami, jeśli tak, proszę mnie poprawić. Zasadniczo chciałbym wiedzieć, czy maksymalne cięcie (z dowolnymi wagami) można skutecznie rozwiązać dla DAG, czy nie.

George

Aby to zadziałało, musisz zmienić pierwszą nierówność na równość: . Wciąż nie rozumiem, dlaczego to zawodzi, ale może coś mi brakuje. Nie myślałem o tym dużo.

d_{i j} = p_{j} - p_{i}

$d_{ij} = p_j - p_i$

Peter Shor

Prawdopodobnie to ja czegoś tu brakuje. Czy to gwarantuje, że wszystkie przyjmują wartości całkowite? Można powiązać z góry za pomocą 1, ale nie jestem pewien, czy to działa, czy nie. Problem wydaje się polegać na tym, że jeśli można to rozwiązać, można zredukować maksymalne cięcie poprzez odwrócenie obciążników krawędzi, co nie powinno być możliwe, ponieważ maksymalne cięcie jest trudne NP. Jednak mogę się tutaj mylić.

p_{i}

$p_i$

p_{i}

$p_i$

George,

Czy st Max-cut NP-hard dla DAG? Jeśli wykres nie jest DAG, nie możesz zmienić tej nierówności na równość, ponieważ potrzebujesz nierówności, jeśli występują cykle. Tak więc w ogólnym przypadku LP nie działa z ujemnymi wagami.

Peter Shor,

Odpowiedzi:

Udoskonaliłeś swój problem w komentarzach. Mówiąc ściślej, masz DAG ze wszystkimi krawędziami odpływającymi ze źródła kierunku ujścia (to znaczy wszystkie krawędzie znajdują się na ścieżce od do ). Chcesz znaleźć minimalne cięcie między dwoma kawałkami DAG, gdzie pierwszy kawałek jest podłączony do , a drugi podłączony do . W przypadku tego problemu działa wariant standardowego algorytmu programowania liniowego dla MIN-CUT, nawet z ujemnymi wagami krawędzi. $s$ $t$ $s$ $t$ $s$ $t$

Używamy tego samego zapisu, co w Wikipedii . Koszt przewagi wynosi . Umieszczamy potencjalną funkcję na każdym węźle i pozwalamy . LP to $(i,j)$ $c_{ij}$ $p_i$ $d_{ij} = p_i - p_j$

\begin{aligned} m i n i m i z e & \sum_{(i, j) \in E} c_{i j} d_{i j} \\ s u b j e c t t o & d_{i j} = p_{i} - p_{j} \forall (i, j) \in E \\ d_{i j} \geq 0 \forall (i, j) \in E \\ p_{s} = 1 \\ p_{t} = 0 \end{aligned}

$\begin{align*} \mathrm{minimize\ } & \sum_{(i,j) \in E} c_{ij} d_{ij} \\ \mathrm{subject\ to\ } & \ \ \ d_{ij} = p_i - p_j \ \ \forall (i,j) \in E \\ &\ \ \ d_{ij} \geq 0 \ \ \ \ \ \ \ \ \ \ \ \, \forall (i,j) \in E \\ & \ \ \ p_s\, = 1 \\ & \ \ \ p_t \, = 0 \end{align*}$

Te równania gwarantują, że , ponieważ każdy wierzchołek jest na pewnej ścieżce - . Podobnie, ponieważ jest nieujemne, potencjały na dowolnej ścieżce od do maleją. Wciąż musimy pokazać, że nie jest optymalnym rozwiązaniem LP ze wszystkimi albo albo . Wynika to z faktu, że wartość rozwiązania LP powyżej jest wartością oczekiwaną cięcia , gdzie wybiera się losowo w , a gdzie cięcie uzyskuje się poprzez umieszczenie wszystkich wierzchołków $0 \leq p_i \leq 1$ $s$ $t$ $d_{ij} = p_i - p_j$ $s$ $t$ $p_i$ $0$ $1$ $C_w$ $w$ $[0,1]$ $C_w$ $i$ z w pierwszym zestawie wierzchołków, a wszystkie wierzchołki z w drugim zestawie. $p_i\geq w$ $p_i < w$

Peter Shor
źródło

Dzięki za doskonałą odpowiedź, Peter. Na pierwszy rzut oka nie było oczywiste, że , ale myślę, że mam. Mam jednak problem ze zrozumieniem argumentu dotyczącego rozwiązania integralnego.

0 \leq p_{i} l e q 1

$0 \leq p_i leq 1$

George

@George: to ten sam argument, który pokazuje, że zwykły Min-Cut LP ma zintegrowane rozwiązania. Gdzieś w Internecie powinno być dłuższe (i bardziej zrozumiałe) wyjaśnienie.

Peter Shor,

Ok, szukam tego. Jeszcze raz bardzo dziękuję za pomoc!

George,