Minimalne cięcie k

W matematyce minimalny k -cut jest kombinatoryczną optymalizacją problemu, który wymaga znalezienia zestawu krawędzi, których usunięcie podzieliłoby graf na co najmniej k połączonych elementów. Te krawędzie są określane jako k -cut . Celem jest znalezienie k -cięcia o minimalnej wadze. To partycjonowanie może mieć zastosowanie w VLSI , eksploracji danych , elementach skończonych i komunikacji w obliczeniach równoległych .

Definicja formalna

Dany jest graf nieskierowany G = ( V , E ) z przypisaniem wag krawędziom w : E → N i liczbą całkowitą k ∈ {2, 3, …, | V |}, podziel V na k zbiorów rozłącznych F = { C ₁ , C ₂ , …, C _k } minimalizując

\ Displaystyle \ suma _ {i = 1} ^ {k- 1}\sum _{j=i+1}^{k}\sum _{\begin{małamacierz}v_{1}\in C_{i}\\v_{2}\in C_{j}\end{ małamacierz}}w(\left\{v_{1},v_{2}\right\})}

Dla ustalonego k problem jest rozwiązywany w czasie wielomianowym w O (| V | ^{k ²} ). Jednak problem jest NP-zupełny, jeśli k jest częścią danych wejściowych. Jest również NP- $,$ jeśli określimy $poprosimy$ o minimalne -cięcie, które oddziela te wierzchołki między każdym ze zbiorów.

przybliżenia

kilka algorytmów aproksymacji z przybliżeniem 2 - 2/ k . Prosty algorytm zachłanny , który osiąga ten współczynnik przybliżenia, oblicza minimalne cięcie w każdym z połączonych komponentów i usuwa najcięższy. Algorytm ten wymaga w sumie n − 1 obliczeń maksymalnego przepływu . Inny algorytm osiągający tę samą gwarancję wykorzystuje reprezentację minimalnych cięć w drzewie Gomory-Hu . Skonstruowanie drzewa Gomory-Hu wymaga n − 1 obliczeń maksymalnego przepływu, ale algorytm wymaga całkowitych obliczeń O ( kn ) maksymalnego przepływu. Jednak łatwiej jest przeanalizować współczynnik aproksymacji drugiego algorytmu. Co więcej, zgodnie z hipotezą ekspansji małego zbioru (przypuszczenie ściśle związane z hipotezą unikalnych gier ), problem jest NP-trudny do przybliżenia do czynnika dla każdej stałej ${\ Displaystyle \ epsilon > 0}$ ${\ Displaystyle (2- \ epsilon)}$ , co oznacza, że wyżej wymienione algorytmy aproksymacji są zasadniczo ciasne dla dużych ${\ displaystyle k}$ .

Wariant problemu wymaga minimalnej wagi k -cut, gdzie partycje wyjściowe mają z góry określone rozmiary. Ten wariant problemu można przybliżyć z dokładnością do współczynnika 3 dla dowolnego ustalonego k , jeśli ograniczy się wykres do przestrzeni metrycznej, co oznacza pełny wykres , który spełnia nierówność trójkąta . Niedawno odkryto wielomianowe schematy aproksymacji czasu (PTAS) dla tych problemów.

Podczas gdy minimalny problem k-Cut jest W[1]-hard sparametryzowany przez k , dla tego parametru można otrzymać sparametryzowany schemat aproksymacji .

Zobacz też

Notatki

^ Goldschmidt & Hochbaum 1988 .
Bibliografia _
^ [1] , który cytuje [2]
^ Saran i Vazirani 1991 .
^ Vazirani 2003 , s. 40–44.
Bibliografia _
^ Guttmann-Beck i Hassin 1999 , s. 198–207.
^ Fernandez de la Vega, Karpiński i Kenyon 2004
^ G. Downey, Rodney; Estivill-Castro, Władimir; Stypendyści, Michael; Prieto, Elena; Rosamunda, Frances A. (2003-04-01). „Cięcie jest trudne: sparametryzowana złożoność k-Cut i powiązane problemy” . Notatki elektroniczne w informatyce teoretycznej . CATS'03, Computing: Australasian Theory Symposium. 78 : 209–222. doi : 10.1016/S1571-0661(04)81014-4 . ISSN 1571-0661 .
^ Loksztanow, Daniel; Saurabh, Saket; Surianarayanan, Vaishali (2022-04-25). „Sparametryzowany schemat aproksymacji dla Min $ k $ -Cut” . SIAM Journal on Computing : FOCS20–205. ar Xiv : 2005.00134 . doi : 10.1137/20M1383197 . ISSN 0097-5397 .

Goldschmidt, O.; Hochbaum, DS (1988), Proc. 29 Ann. Symp. IEEE na temat podstaw informatyki. nauka , IEEE Computer Society, s. 444–451
Garey, MR; Johnson, DS (1979), Komputery i nieustępliwość: przewodnik po teorii NP-zupełności , WH Freeman, ISBN 978-0-7167-1044-8
Saran, H.; Vazirani, V. (1991), „Finding k -cuts w obrębie dwukrotnie optymalnego” , Proc. 32. Ann. Symp. IEEE na temat podstaw informatyki. Sci , IEEE Computer Society, s. 743–751
Vazirani, Vijay V. (2003), Algorytmy aproksymacji , Berlin: Springer, ISBN 978-3-540-65367-7
Guttmann-Beck, N.; Hassin, R. (1999), „Algorytmy aproksymacji dla minimalnego k -cięcia” (PDF) , Algorithmica , s. 198–207
Comellas, Francesc; Sapena, Emili (2006), „Algorytm wieloagentowy do partycjonowania grafów. Notatki z wykładów w Comput. Sci”. , Algorytmica , 3907 (2): 279–285, Citeseerx 10.1.1.55.5697 , DOI : 10.1007/S004530010013 , ISSN 0302-9743 , S2cid 25721784 , archiwizowany z oryginału w dniu 2009-12-12
Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnus; Karpiński, Marek ; Woeginger, Gerhard (2000), „Minimum k-cut”, Kompendium problemów optymalizacji NP
Fernandez de la Vega, W.; Karpiński, M.; Kenyon, C. (2004). „Schematy aproksymacji dla metrycznego bisekcji i partycjonowania” . Materiały z piętnastego dorocznego sympozjum ACM-SIAM na temat algorytmów dyskretnych . s. 506–515.
Manurangsi, P. (2017). „Nieprzybliżenie maksymalnego bikliki krawędzi, maksymalnego zrównoważonego bikliki i minimalnego k-Cut z hipotezy ekspansji małego zbioru”. 44th International Colloquium on Automata, Languages and Programming, ICALP 2017 . s. 79:1–79:14. doi : 10.4230/LIPIcs.ICALP.2017.79 .

[1] Goldschmidt & Hochbaum 1988 .

[2] Bibliografia _

[3] [1] , który cytuje [2]

[4] Saran i Vazirani 1991 .

[5] Vazirani 2003 , s. 40–44.

[6] Bibliografia _

[7] Guttmann-Beck i Hassin 1999 , s. 198–207.

[8] Fernandez de la Vega, Karpiński i Kenyon 2004

[9] G. Downey, Rodney; Estivill-Castro, Władimir; Stypendyści, Michael; Prieto, Elena; Rosamunda, Frances A. (2003-04-01). „Cięcie jest trudne: sparametryzowana złożoność k-Cut i powiązane problemy” . Notatki elektroniczne w informatyce teoretycznej . CATS'03, Computing: Australasian Theory Symposium. 78 : 209–222. doi : 10.1016/S1571-0661(04)81014-4 . ISSN 1571-0661 .

[10] Loksztanow, Daniel; Saurabh, Saket; Surianarayanan, Vaishali (2022-04-25). „Sparametryzowany schemat aproksymacji dla Min $ k $ -Cut” . SIAM Journal on Computing : FOCS20–205. ar Xiv : 2005.00134 . doi : 10.1137/20M1383197 . ISSN 0097-5397 .