I Multiterminal Cut problemet får vi en kant-viktad graf och en delmängd av hörnen kallas terminaler, och bad om en minsta vikt uppsättning kanter som skiljer varje terminal från alla andra. När antalet k av terminaler är två, är detta helt enkelt mincut, max-flow problem, och kan lösas i polynom tid. Vi visar att problemet blir NP-hård så snart som k = 3, men kan lösas i polynom tid för planar grafer för alla fasta k. Planar problemet är NP-hard, dock om k inte är fast. Vi beskriver också en enkel approximationsalgoritm för godtyckliga grafer som garanterat kommer att ligga inom en faktor på 2 − 2/ k av optimal skärvikt.
Men om r är godtycklig då problemet är NP-hård även när G är planar REF.
The Complexity of Multiterminal Cuts
{'venue': 'SIAM Journal on Computing', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}