Minsta k -snitt

Inom matematik är minimum k -cut ett kombinatoriskt optimeringsproblem som kräver att man hittar en uppsättning kanter vars borttagning skulle dela upp grafen till minst k anslutna komponenter. Dessa kanter kallas k -cut . Målet är att hitta minimivikten k -cut. Denna partitionering kan ha applikationer inom VLSI- design, data-mining , finita element och kommunikation i parallell beräkning .

Formell definition

Givet en oriktad graf G = ( V , E ) med en tilldelning av vikter till kanterna w : E → N och ett heltal k ∈ {2, 3, …, | V |}, dela upp V i k disjunkta uppsättningar F = { C ₁ , C ₂ , …, C _k } under minimering

\sum _{i=1}^{k- 1}\summa _{j=i+1}^{k}\summa _{\begin{smallmatrix}v_{1}\in C_{i}\\v_{2}\in C_{j}\end{ smallmatrix}}w(\left\{v_{1},v_{2}\right\})

För en fix k är problemet polynomtid lösbart i O (| V | ^{k ²} ). Problemet är dock NP-komplett om k är en del av ingången. Det är också NP-komplett om vi specificerar $k$ hörn och ber om minsta $k$ -cut som skiljer dessa hörn mellan var och en av uppsättningarna.

Uppskattningar

flera approximationsalgoritmer med en approximation på 2 − 2/ k . En enkel girig algoritm som uppnår denna approximationsfaktor beräknar ett minimisnitt i var och en av de anslutna komponenterna och tar bort den tyngsta. Denna algoritm kräver totalt n − 1 maxflödesberäkningar . En annan algoritm som uppnår samma garanti använder Gomory-Hu-trädrepresentationen av minimisnitt. Att konstruera Gomory–Hu-trädet kräver n − 1 maxflödesberäkningar, men algoritmen kräver en övergripande O ( kn ) maxflödesberäkning. Ändå är det lättare att analysera approximationsfaktorn för den andra algoritmen. Dessutom, under Small Set Expansion Hypothesis (en gissning som är nära relaterad till Unique Games Conjecture ), är problemet NP-svårt att approximera till inom $(2-\epsilon )$ faktor för varje konstant $\epsilon >0$ , vilket betyder att de tidigare nämnda approximationsalgoritmerna är väsentligen snäva för stora $k$ .

En variant av problemet kräver en minimivikt k -cut där utgångspartitionerna har fördefinierade storlekar. Denna problemvariant är ungefärlig till inom en faktor 3 för varje fast k om man begränsar grafen till ett metriskt utrymme, vilket betyder en komplett graf som uppfyller triangelolikheten . På senare tid upptäcktes polynomiska tidsapproximationsscheman (PTAS) för dessa problem.

Medan det minsta k-Cut-problemet är W[1]-hårt parametriserat av k , kan ett parametriserat approximationsschema erhållas för denna parameter.

Se även

Anteckningar

^ Goldschmidt & Hochbaum 1988 .
^ Garey & Johnson 1979
^ [1] , som citerar [2]
^ Saran & Vazirani 1991 .
^ Vazirani 2003 , s. 40–44.
^ Manurangsi 2017
^ Guttmann-Beck & Hassin 1999 , s. 198–207.
^ Fernandez de la Vega, Karpinski & Kenyon 2004
^ G. Downey, Rodney; Estivill-Castro, Vladimir; Fellows, Michael; Prieto, Elena; Rosamund, Frances A. (2003-04-01). "Att skära upp är svårt att göra: den parametriserade komplexiteten hos k-Cut och relaterade problem" . Elektroniska anteckningar i teoretisk datavetenskap . CATS'03, Computing: the Australasian Theory Symposium. 78 : 209-222. doi : 10.1016/S1571-0661(04)81014-4 . ISSN 1571-0661 .
^ Lokshtanov, Daniel; Saurabh, Saket; Surianarayanan, Vaishali (2022-04-25). "Ett parametriserat approximationsschema för Min $k$-Cut" . SIAM Journal on Computing : FOCS20–205. arXiv : 2005.00134 . doi : 10.1137/20M1383197 . ISSN 0097-5397 .

Goldschmidt, O.; Hochbaum, DS (1988), Proc. 29:e Ann. IEEE Symp. på Foundations of Comput. Sci. , IEEE Computer Society, s. 444–451
Garey, MR; Johnson, DS (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , WH Freeman, ISBN 978-0-7167-1044-8
Saran, H.; Vazirani, V. (1991), "Hitta k -snitt inom två gånger det optimala", Proc . 32:a Ann. IEEE Symp. på Foundations of Comput. Sci , IEEE Computer Society, s. 743–751
Vazirani, Vijay V. (2003), Approximation Algorithms , Berlin: Springer, ISBN 978-3-540-65367-7
Guttmann-Beck, N.; Hassin, R. (1999), "Approximation algorithms for minimum k -cut" (PDF) , Algorithmica , s. 198–207
Comellas, Francesc; Sapena, Emili (2006), "En multiagentalgoritm för grafpartitionering. Lecture Notes in Comput. Sci." , Algorithmica , 3907 (2): 279–285, CiteSeerX 10.1.1.55.5697 , doi : 10.1007/s004530010013 , ISSN 0302-9743 , S2CID 725 från originalet 725 - 9007 från originalet 12
Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek ; Woeginger, Gerhard (2000), "Minimum k-cut", A Compendium of NP Optimization Problems
Fernandez de la Vega, W.; Karpinski, M.; Kenyon, C. (2004). "Approximationsscheman för metrisk halvering och partitionering" . Proceedings från det femtonde årliga ACM-SIAM-symposiet om diskreta algoritmer . s. 506–515.
Manurangsi, P. (2017). "Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique och Minimum k-Cut från Small Set Expansion Hypothesis". 44:e internationella kollokviet om automater, språk och programmering, ICALP 2017 . s. 79:1–79:14. doi : 10.4230/LIPIcs.ICALP.2017.79 .

[1] Goldschmidt & Hochbaum 1988 .

[2] Garey & Johnson 1979

[3] [1] , som citerar [2]

[4] Saran & Vazirani 1991 .

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

[6] Manurangsi 2017

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

[8] Fernandez de la Vega, Karpinski & Kenyon 2004

[9] G. Downey, Rodney; Estivill-Castro, Vladimir; Fellows, Michael; Prieto, Elena; Rosamund, Frances A. (2003-04-01). "Att skära upp är svårt att göra: den parametriserade komplexiteten hos k-Cut och relaterade problem" . Elektroniska anteckningar i teoretisk datavetenskap . CATS'03, Computing: the Australasian Theory Symposium. 78 : 209-222. doi : 10.1016/S1571-0661(04)81014-4 . ISSN 1571-0661 .

[10] Lokshtanov, Daniel; Saurabh, Saket; Surianarayanan, Vaishali (2022-04-25). "Ett parametriserat approximationsschema för Min $k$-Cut" . SIAM Journal on Computing : FOCS20–205. arXiv : 2005.00134 . doi : 10.1137/20M1383197 . ISSN 0097-5397 .