Login
Login

Minimum k-cut

{{Short description|Combinatorial optimization graph problem}}

{{For|the Canadian record producer and DJ|K-Cut}}

{{DISPLAYTITLE:Minimum k-cut}}

In mathematics, the minimum {{mvar|k}}-cut is a combinatorial optimization problem that requires finding a set of edges whose removal would partition the graph to at least {{mvar|k}} connected components. These edges are referred to as {{mvar|k}}-cut. The goal is to find the minimum-weight {{mvar|k}}-cut. This partitioning can have applications in VLSI design, data-mining, finite elements and communication in parallel computing.

File:Minimum k-cut.svg

Formal definition

Given an undirected graph {{math|1=G = (V, E)}} with an assignment of weights to the edges {{math|w: E → N}} and an integer k \in \{2,3, \ldots, |V|\}, partition {{mvar|V}} into {{mvar|k}} disjoint sets F = \{ C_1,C_2,\ldots,C_k \} while minimizing

: \sum_{i=1}^{k-1} \ \sum_{j=i+1}^k \sum_{\begin{smallmatrix} v_1 \in C_i \\ v_2 \in C_j \end{smallmatrix}} w ( \left \{ v_1, v_2 \right \} ).

For a fixed {{mvar|k}}, the problem is polynomial time solvable in O \bigl(|V|^{k^2} \bigr).{{harvnb|Goldschmidt|Hochbaum|1988}}. However, the problem is NP-complete if {{mvar|k}} is part of the input.{{harvnb|Garey|Johnson|1979}} It is also NP-complete if we specify {{mvar|k}} vertices and ask for the minimum {{mvar|k}}-cut which separates these vertices among each of the sets.[https://www.jstor.org/stable/3690374?seq=13], which cites [http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.6534]

Approximations

Several approximation algorithms exist with an approximation of 2-\tfrac 2 k. A simple greedy algorithm that achieves this approximation factor computes a minimum cut in each of the connected components and removes the lightest one. This algorithm requires a total of {{math|n − 1}} max flow computations. Another algorithm achieving the same guarantee uses the Gomory–Hu tree representation of minimum cuts. Constructing the Gomory–Hu tree requires {{math|n − 1}} max flow computations, but the algorithm requires an overall {{math|O(kn)}} max flow computations. Yet, it is easier to analyze the approximation factor of the second algorithm.{{harvnb|Saran|Vazirani|1991}}.{{harvnb|Vazirani|2003|pp=40–44}}. Moreover, under the small set expansion hypothesis (a conjecture closely related to the unique games conjecture), the problem is NP-hard to approximate to within {{math|(2 − ε)}} factor for every constant {{math|ε > 0}},{{harvnb|Manurangsi|2017}} meaning that the aforementioned approximation algorithms are essentially tight for large {{mvar|k}}.

A variant of the problem asks for a minimum weight {{mvar|k}}-cut where the output partitions have pre-specified sizes. This problem variant is approximable to within a factor of 3 for any fixed {{mvar|k}} if one restricts the graph to a metric space, meaning a complete graph that satisfies the triangle inequality.{{harvnb|Guttmann-Beck|Hassin|1999|pp=198–207}}. More recently, polynomial time approximation schemes (PTAS) were discovered for those problems.{{harvnb|Fernandez de la Vega|Karpinski|Kenyon|2004}}

While the minimum {{mvar|k}}-cut problem is W[1]-hard parameterized by {{mvar|k}},{{Cite journal |last1=G. Downey |first1=Rodney |last2=Estivill-Castro |first2=Vladimir |last3=Fellows |first3=Michael |last4=Prieto |first4=Elena|author4-link=Elena Prieto-Rodriguez |last5=Rosamund |first5=Frances A. |date=2003-04-01 |title=Cutting Up Is Hard To Do: The Parameterised Complexity of k-Cut and Related Problems |journal=Electronic Notes in Theoretical Computer Science |series=CATS'03, Computing: the Australasian Theory Symposium |language=en |volume=78 |pages=209–222 |doi=10.1016/S1571-0661(04)81014-4 |issn=1571-0661|doi-access=free |hdl=10230/36518 |hdl-access=free }} a parameterized approximation scheme can be obtained for this parameter.{{Cite journal |last1=Lokshtanov |first1=Daniel |last2=Saurabh |first2=Saket |last3=Surianarayanan |first3=Vaishali |date=2022-04-25 |title=A Parameterized Approximation Scheme for Min $k$-Cut |url=https://epubs.siam.org/doi/10.1137/20M1383197 |journal=SIAM Journal on Computing |pages=FOCS20–205 |doi=10.1137/20M1383197 |arxiv=2005.00134 |issn=0097-5397}}

See also

Notes

References

  • {{citation

| first1=O.

| last1=Goldschmidt

| first2=D. S.

| last2=Hochbaum | author2-link = Dorit S. Hochbaum

| title=Proc. 29th Ann. IEEE Symp. on Foundations of Comput. Sci.

| publisher=IEEE Computer Society

| year=1988

| pages=444–451 }}

  • {{citation

| first1=M. R.

| last1=Garey

| first2=D. S.

| last2=Johnson

| title=Computers and Intractability: A Guide to the Theory of NP-Completeness

| publisher = W.H. Freeman

| year=1979

| isbn = 978-0-7167-1044-8 }}

  • {{citation

| first1=H.

| last1=Saran

| first2=V.

| last2=Vazirani

| contribution=Finding k-cuts within twice the optimal

| contribution-url=http://www.cc.gatech.edu/~vazirani/k-cut.ps

| title=Proc. 32nd Ann. IEEE Symp. on Foundations of Comput. Sci

| publisher=IEEE Computer Society

| year=1991

| pages=743–751 }}

  • {{citation

| last = Vazirani

| first = Vijay V.

| author-link = Vijay Vazirani

| title = Approximation Algorithms

| publisher = Springer

| year = 2003

| location = Berlin

| isbn = 978-3-540-65367-7 }}

  • {{citation

| last1 = Guttmann-Beck

| first1 = N.

| last2 = Hassin

| first2 = R.

| contribution = Approximation algorithms for minimum k-cut

| contribution-url = http://www.math.tau.ac.il/~hassin/k_cut_00.pdf

| title = Algorithmica

| year = 1999

| pages = 198–207 }}

  • {{citation

|last1 = Comellas

|first1 = Francesc

|last2 = Sapena

|first2 = Emili

|title = A multiagent algorithm for graph partitioning. Lecture Notes in Comput. Sci.

|year = 2006

|volume = 3907

|pages = 279–285

|issn = 0302-9743

|doi = 10.1007/s004530010013

|journal = Algorithmica

|issue = 2

|url = http://www-ma4.upc.es/~comellas/evocomnet06/CoSa06-EvoCOMNET06.html

|url-status = dead

|archive-url = https://web.archive.org/web/20091212080856/http://www-ma4.upc.es/~comellas/evocomnet06/CoSa06-EvoCOMNET06.html

|archive-date = 2009-12-12

|citeseerx = 10.1.1.55.5697

|s2cid = 25721784

}}

  • {{citation

| last1=Crescenzi | first1=Pierluigi

| last2=Kann | first2=Viggo

| last3=Halldórsson | first3=Magnús

| last4=Karpinski | first4=Marek | author-link4=Marek Karpinski

| last5=Woeginger | first5=Gerhard | author-link5 = Gerhard J. Woeginger

| title=A Compendium of NP Optimization Problems

| contribution=Minimum k-cut

| url=http://www.csc.kth.se/~viggo/wwwcompendium/node90.html

| year=2000 }}

  • {{Cite conference

| title=Approximation schemes for Metric Bisection and partitioning

| last1=Fernandez de la Vega | first1=W.

| last2=Karpinski | first2 = M.

| last3=Kenyon | first3=C. | author3-link = Claire Mathieu

| book-title=Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete Algorithms

| pages=506–515

| year=2004

| url=http://dl.acm.org/citation.cfm?id=982792.982864

}}

  • {{Cite conference

| title=Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique and Minimum k-Cut from the Small Set Expansion Hypothesis

| last=Manurangsi | first=P.

| book-title=44th International Colloquium on Automata, Languages, and Programming, ICALP 2017

| pages=79:1–79:14

| year=2017

| doi=10.4230/LIPIcs.ICALP.2017.79 | doi-access=free }}

Category:NP-complete problems

Category:Combinatorial optimization

Category:Computational problems in graph theory

Category:Approximation algorithms