Relaksacja LP niezależnego zestawu

13

Próbowałem następującej relaksacji LP maksymalnie niezależnego zestawu

max \sum_{i} x_{i}

$\max \sum_i x_i$

s.t. x_{i} + x_{j} \leq 1 \forall (i, j) \in E

$\text{s.t.}\ x_i+x_j\le 1\ \forall (i,j)\in E$

x_{i} \geq 0

$x_i\ge 0$

Dostaję $1/2$ za każdą zmienną za każdy sześcienny dwudzielny wykres, który próbowałem.

Czy to prawda dla wszystkich połączonych sześciennych dwudzielnych grafów?
Czy istnieje relaksacja LP, która działa lepiej dla takich wykresów?

Aktualizacja 03/05 :

Oto wynik relaksacji LP opartej na klice, sugerowanej przez Nathana

Podsumowałem tutaj eksperymenty. Co ciekawe, wydaje się, że istnieje całkiem sporo dwudzielnych grafów, dla których integracja najprostszego LP jest integralna.

graph-theory co.combinatorics linear-programming

— Jarosław Bułatow
źródło

Rozwiązanie pewnością nie jest unikalne. Na sześciennym grafie dwustronnym można uzyskać optymalne rozwiązanie z w jednej części i w drugiej części.

x_{i} = 1 / 2

$x_i = 1/2$

x_{i} = 1

$x_i = 1$

x_{i} = 0

$x_i = 0$

— Jukka Suomela

1

Przepraszam, brakowało mi ważnej części, rozważam tylko dwustronne wykresy sześcienne. Każdy dwustronny wykres sześcienny, który wypróbowałem, miał integralne rozwiązanie

— Jarosław Bułatow

Musisz także dodać „podłączony”, jeśli chcesz uniknąć nietypowych rozwiązań.

— Jukka Suomela

2

(1) Zapomniałeś napisać ograniczenia nieujemności. (2) W przypadku grafów dwustronnych optymalna wartość relaksacji LP jest zawsze równa maksymalnemu rozmiarowi niezależnego zestawu. Jest to bezpośredni następstwo twierdzenia Königa .

— Tsuyoshi Ito

2

@Yaroslav: Pytanie poboczne: jak narysować te wykresy?

— Tim

16

Niepowiązane dwustronne wykresy sześcienne mają unikalne optymalne rozwiązanie ; na dwustronnym wykresie sześciennym masz integralne optymalne rozwiązanie. $x_i = 1/2$

Dowód: na wykresie sześciennym, jeśli wszystkie ograniczenia , masz , a zatem optymalne jest co najwyżej . $3n/2$ $x_i + x_j \le 1$ $\sum_i 3 x_i \le 3n/2$ $n/2$

Rozwiązanie dla wszystkich jest banalnie wykonalne, a zatem również optymalne. $x_i = 1/2$ $i$

Na dwustronnym grafie sześciennym każda część ma połowę węzłów, a zatem rozwiązanie w jednej części jest również optymalne. $x_i = 1$

Każde optymalne rozwiązanie musi być ścisłe, tzn. Musimy mieć a zatem dla każdej krawędzi . Zatem jeśli masz nieparzysty cykl, musisz wybrać dla każdego węzła w cyklu. A następnie, jeśli wykres jest podłączony, ten wybór jest propagowany wszędzie. $\sum_i 3 x_i = 3n/2$ $x_i + x_j = 1$ $\{i,j\}$ $x_i = 1/2$

— Jukka Suomela
źródło

2

Jak napisałem w komentarzu do pytania, potrzebujesz tylko dwustronności, aby udowodnić istnienie integralnego optymalnego rozwiązania (ale wymaga to innego dowodu niż twój).

— Tsuyoshi Ito

@Tsuyoshi: Tak, twierdzenie Königa dobrze jest pamiętać. Na przykład, wraz z powyższą obserwacją, pokaże, że każdy dwustronny wykres sześcienny ma 1-faktoryzację (tj. Może być podzielony na trzy idealne dopasowania). Oczywiście jest to „zły” sposób na udowodnienie tego wyniku, ale myślę, że ładnie pokazuje on moc twierdzenia Königa - jeśli tylko pamiętacie twierdzenie Königa, istnieje wiele klasycznych wyników w teorii grafów, które można następnie łatwo wymyślić na nowo .

— Jukka Suomela

12

Ten LP jest w połowie zintegrowany dla wszystkich wykresów, tzn. Istnieje optymalne rozwiązanie, w którym każda zmienna jest w {0,1 / 2,1}. Wynika to po prostu z twierdzenia Nemhausera i Kłusaka. Oczywiście ten sam wniosek o połowie integralności wynika z LP problemu dopełniacza (pokrycie wierzchołków). Gdy wykres jest dwustronny, rozwiązanie jest integralne. Wynika to po prostu z twierdzenia o maksymalnym przepływie min-cut lub pracy z ekstremalnymi punktowymi rozwiązaniami tego LP. Również 1/2 krawędzi tworzą nieparzysty cykl.

Oczywiście ten LP nie jest dobry do rozwiązania problemu IS. Dodanie ograniczeń Kliki lub SDP jest znacznie lepszym podejściem.

Wypełnienia wierzchołków: właściwości strukturalne i algorytmy GL Nemhauser i Trotter-Math. Program., 1975

— Mohit Singh
źródło

Racja, zobacz także Twierdzenie 5.6 tego artykułu, dotyczące bardzo prostego algorytmu, który skutecznie znajduje rozwiązanie półintegralne.

— Jukka Suomela

LP z ograniczeniami Clique rozwiązało około 50% więcej wykresów z zestawu powyżej ... gdzie mogę znaleźć sformułowanie SDP?

— Yaroslav Bulatov

7

Praca doktorska Sergiy Butenko z 2003 r. Zawiera przegląd innych relaksacji LP MIS, a także relaksacji kwadratowych.

— Suresh Venkat
źródło

6

Istnieje inny sposób uzyskania „zrelaksowanej wersji maksymalnego niezależnego zestawu”. Zamiast mieć jako ograniczenia „dla każdej krawędzi, suma wynosi co najwyżej 1”, ograniczenia są „dla każdego pełnego podgrafu, krawędź wynosi co najwyżej 1”. Co oznacza: dla każdej krawędzi, dla każdego trójkąta, dla każdego i tak dalej. $K_4$

Nazywa się to ułamkowym niezależnym numerem zestawu. Znajdziesz tam trochę informacji: http://en.wikipedia.org/wiki/Fractional_coloring lub w książce „Teoria grafów frakcyjnych” Daniela Ullmana i Edwarda Scheinermana ( http://www.ams.jhu.edu/~ers / fgt / ).

Praktycznie ta formuła jest trudna do obliczenia NP, mimo że wszystkie zmienne są ciągłe -> liczba kliknięć jest wykładnicza i trudna do obliczenia ... Ale możesz wyliczyć tylko niektóre specjalne kliky, na przykład po prostu krawędzie (które właśnie zrobiłeś) lub krawędzie + trójkąty lub wszystkie kliki do . W końcu wartość może stać się „bardziej reprezentatywna” dla rzeczywistej wartości całkowitej (*) :-) $K_k$

Nathann

(*) to powiedziawszy, teoretycznie masz dowolną dużą różnicę między optymalnym wynikiem w LP, w którym wszystkie kliki są reprezentowane, a optymalnym niezależnym zbiorem

— Nathann Cohen
źródło

1

Jednym z problemów związanych z tym podejściem jest to, że jeśli masz dwudzielny graf sześcienny bez trójkątów (a jest ich mnóstwo ...), sformułowanie jest dokładnie takie samo jak w pytaniu, a my mamy dokładnie to samo złe wieści. Mówiąc bardziej ogólnie, myślę, że zawsze możemy konstruować wykresy, w których wszystkie węzły są w kliku i nie ma -kliki, i pokazują, że dla wszystkich jest unikalnym optymalnym rozwiązaniem LP.

k

$k$

(k + 1)

$(k+1)$

x_{i} = 1 / k

$x_i = 1/k$

i

$i$

— Jukka Suomela

ciekawe, wydaje się, że jest to związane z łatwością IndependentSet na wykresach akordowych

— Yaroslav Bulatov

Przeprowadziłem kilka eksperymentów, a rozwiązanie tego relaksacji LP zawsze było integralną częścią grafów akordowych

— Jarosław Bułatow

1

@YaroslavBulatov Jest powód twojej obserwacji. Nierówności kliki i granice nieujemności zapewniają wypukły kadłub niezależnych zbiorów wtedy i tylko wtedy, gdy wykres jest idealny. Wykresy akordowe są idealne.

— Austin Buchanan,