Interesujące funkcje na wykresach, które można skutecznie zmaksymalizować.

Powiedz, że mam wykres ważony $G = (V,E,w)$ taki, że $w:E\rightarrow [-1,1]$ jest funkcją ważenia - zwróć uwagę, że dopuszczalne są wagi ujemne.

Powiedzieć, że $f:2^V\rightarrow \mathbb{R}$ definiuje właściwość każdego podzbioru wierzchołków $S \subset V$ .

$f$$\arg\max_{S \subseteq V}f(S)$

Na przykład funkcja cięcia wykresu jest interesującą właściwością podzbiorów wierzchołków, ale nie można go skutecznie zmaksymalizować. Funkcja gęstości krawędzi to kolejny przykład interesującej właściwości, której niestety nie można skutecznie zmaksymalizować. Szukam funkcji, które są równie interesujące, ale można je skutecznie zmaksymalizować.

Pozwolę, by definicja „interesujący” była nieco niejasna, ale chcę, aby problem maksymalizacji nie był trywialny. Na przykład nie powinno być tak, że można ustalić odpowiedź bez badania krawędzi wykresu (więc funkcje stałe i funkcja liczności nie są interesujące). Nie powinno być również tak, że tak naprawdę koduje tylko jakąś inną funkcję z domeną wielomianową, wstawiając ją do domeny (tzn. Nie chcę, aby istniała jakaś mała domena i niektóre funkcje znany przed spojrzeniem na wykres, tak że interesująca funkcja to tak naprawdę , i$f$$2^V$$X$$m:2^S\rightarrow X$$g:X\rightarrow \mathbb{R}$$f(S) = g(m(S))$ W takim przypadku problem „maksymalizacji” jest tak naprawdę tylko kwestią oceny funkcji na wszystkich wejściach.)

Edycja: Prawdą jest, że czasami problemy z minimalizacją są łatwe, jeśli zignorujesz grubości krawędzi (chociaż nie minimalizuję funkcji cięcia, ponieważ dopuszczam ujemne wagi krawędzi). Ale jestem wyraźnie zainteresowany problemami z maksymalizacją. W tym otoczeniu nie staje się to jednak problemem naturalnych problemów ważonych.

Ilekroć zlicza liczbę krawędzi ( u , v ), spełniających pewne orzeczenie logiczna zdefiniowana w kategoriach U ∈ $f(S)$$(u,v)$$u\in S$ i , to co napisałeś, to tylko logiczna 2-CSP. Funkcja celu prosi o maksymalizację liczby spełnionych klauzul we wszystkich przypisaniach do zmiennych. Jest to znane jako NP-twarde, a dokładny próg twardości jest również znany przy założeniu UGC (patrz Raghavendra'08).$v\in S$

Istnieje wiele naturalnych pozytywnych przykładów, gdy chcesz zmaksymalizować ponad podzbiory krawędzi, np. Maksymalne dopasowanie jest w tym przypadku przykładem problemu wielomianowego.

Przegroda domatyczna / słabe zabarwienie 2.

(W tym przypadku jeśli każde v ∈ S ma sąsiada w V ∖ S i vice versa. W przeciwnym razie f ( S ) = 0. Rozwiązanie z f ( S ) = 1 zawsze istnieje, jeśli nie ma izolowanych węzły i można je łatwo znaleźć w czasie wielomianowym).$f(S) = 1$$v \in S$$V \setminus S$$f(S) = 0$$f(S) = 1$

Cięcie minimalne (szczególnie cięcie wierzchołków).

(W tym przypadku byłobymniej więcejtak: 0, jeśli usunięcie węzłów ze zbioru S nie dzieli G na co najmniej dwa składniki, a | V | - | S | w przeciwnym razie. Wtedy maksymalizacja f jest równoważna znalezieniu minimalnego cięcia , co można zrobić w czasie wielomianowym).$f$$S$$G$$|V| - |S|$$f$

Możesz także zdefiniować podobną funkcję, która odpowiada minimalnym cięciom krawędzi.

(Na przykład wynosi 0, jeśli S = ∅ lub S = V ; w przeciwnym razie jest to |$f(S)$$S = \emptyset$$S = V$ , gdzie X jest zbiorem krawędzi, które mają jeden punkt końcowy w S, a drugi punkt końcowy w V ∖ S. )$|E| - |X|$$X$$S$$V \setminus S$

Maksymalny niezależny zestaw.

(Tutaj = liczba węzłów w S , które nie sąsiadują z żadnym innym węzłem w S + liczba węzłów w V ∖ S , które sąsiadują z węzłem w S. Iff S jest maksymalnym niezależnym zestawem, który mamy $f(S)$$S$$S$$V \setminus S$$S$$S$$f(S) = |V|$