Problem wielokrotnego cięcia

12

Szukam nazwy lub jakichkolwiek odniesień do tego problemu.

Biorąc pod uwagę wykres ważony $G = (V, E, w)$ znajdź podział wierzchołków na $n = |V|$ ustawia $S_1,\ldots,S_n$ tak, aby zmaksymalizować wartość przyciętych krawędzi:

c (S_{1}, \dots, S_{n}) = \sum_{i \neq j} (\sum_{(u, v) \in E : u \in S_{i}, v \in S_{j}} w (u, v))

$c(S_1,\ldots,S_n) = \sum_{i \ne j}\left(\sum_{(u,v)\in E : u \in S_i, v \in S_j}w(u,v)\right)$ Zauważ, że niektóre zestawy

S_{i}

$S_i$ mogą być puste. Tak więc problemem jest w zasadzie maks. K-cut, z tym że

k

$k$ nie jest częścią danych wejściowych: algorytm może wybrać dowolne

k

$k$ , tak aby zmaksymalizować wartość krawędzi cięcia. Oczywiście problem jest trywialny, jeśli wagi krawędzi nie są ujemne: po prostu umieść każdy wierzchołek sam w swoim zestawie, a przecinasz wszystkie krawędzie. Ale, aby uczynić rzeczy interesującymi, dozwolone są ujemne krawędzie wagowe.

Czy to badany problem? Doceniamy odniesienia do wyników algorytmu lub twardości!

— Aaron Roth
źródło

2

+ 1

$+1$

- 1

$-1$

G

$G$

\pm 1

$\pm 1$

11

Problemem jest wariant Correlation Clustering (CC) Bansal, N., Blum, A. i Chawla, S. (2004). „Klaster korelacji”. Machine Learning Journal (wydanie specjalne na temat teoretycznych postępów w grupowaniu danych, str. 86–113, doi: 10.1023 / B: MACH.0000033116.57574.95.

$G$ $(v,w)$ $a(v,w)$ $b(v,w)$ $P$ $c_P(v,w)$ $a(v,w)$ $v$ $w$ $P$ $b(v,w)$ $P$ $V$ $\sum_{v,w} c(v,w)$

$a(v,w)=0$ $b(v,w)$ $O(\log n)$

Opisane PTAS opierają się na technice płynnego programowania wielomianowego: w najbardziej ogólnym przypadku nie sądzę, aby twój problem spełniałby wymagania tej techniki.

— Gianluca Della Vedova
źródło

18

Nie znam żadnych odniesień, ale mogę wykazać, że jest kompletny NP, poprzez redukcję zabarwienia wykresu.

Biorąc pod uwagę wykres G i liczbę k kolorów, za pomocą których można pokolorować G, utwórz nowy wykres G ', który składa się z G wraz z k nowych wierzchołków, tak aby każdy nowy wierzchołek był połączony z każdym wierzchołkiem w G. Przypisz wagę + kn do każda krawędź G, waga + kn do każdej krawędzi łączącej dwa z k nowych wierzchołków i waga -1 do każdej krawędzi łączącej k nowych wierzchołków z G.

Następnie, jeśli G może być w kolorze k, zabarwienie (wraz z przegrodą, która przypisuje każdy z nowych wierzchołków jednej z klas kolorów) osiąga całkowitą wagę kn (m + k (k-1) / 2) - (k -1) n.

W przeciwnym kierunku, jeśli masz przegrodę, która osiąga ten całkowity ciężar, musi przeciąć wszystkie krawędzie G i wszystkie krawędzie między parami nowych wierzchołków. Wycięcie wszystkich krawędzi G definiuje kolorystykę G, a przycięcie krawędzi między parami nowych wierzchołków oznacza, że każdy wierzchołek G może przylegać do co najwyżej jednego z k nowych wierzchołków. Dlatego w celu uzyskania optymalnego - (k-1) n ważenia, każdy wierzchołek G musi przylegać dokładnie do jednego z nowych wierzchołków, a zatem może istnieć tylko k klas kolorów w kolorze zdefiniowanym przez przegroda.

Oznacza to, że partycje o podanym ciężarze są w 1-1 zgodne z k-zabarwieniem G, więc określa to redukcję zabarwienia do problemu partycji.

— David Eppstein
źródło

11

Pozwolę sobie uzupełnić ładny dowód kompletności NP Davida, dodając odniesienie do specjalnego przypadku zadanego przez Jukkę w komentarzu do pytania. Jeśli wykres jest kompletnym wykresem, a ciężary krawędzi są ograniczone do ± 1, problem jest równoważny z problemem NP-complete, znanym jako Edycja skupień.

Edycja klastrów to następujący problem wprowadzony przez Shamira, Sharana i Tsura [SST04]. Tutaj wykres skupień jest wykresem będącym połączeniem klik-rozłącznych wierzchołków, a edycja polega na dodaniu lub usunięciu jednej krawędzi.

Instancja edycji klastra : Wykres G = ( V , E ) i liczba całkowita k ∈ℕ.
Pytanie : Czy można zamienić G w wykres klastra o co najwyżej k edycji?

Edycja klastrów jest zakończona NP [SST04].

Aby zobaczyć edytowanie klastrów jest równoważne z wyżej wspomnianym specjalnym przypadkiem bieżącego problemu, niech G = ( V , E ) będzie wykresem. Niech n = | V | i rozważ G jako podgraph pełnego wykresu K _n . K _n , otrzymując masę -1 krawędziom w G i ciężaru +1 do krawędzi nie w G . Następnie G można przekształcić w wykres klastrowy co najwyżej k edycji, tylko wtedy, gdy istnieje partycja ( S ₁ ,…, S _n ) taka, że c ( S ₁ ,…,S _n ) ≥ - | E | - k dla tego ważonego pełnego wykresu K _n . $\binom{n}{2}$

[SST04] Ron Shamir, Roded Sharan i Dekel Tsur. Problemy z modyfikacją wykresów klastrowych. Discrete Applied Mathematics , 144 (1–2): 173–182, listopad 2004. http://dx.doi.org/10.1016/j.dam.2004.01.007

— Tsuyoshi Ito
źródło