Solving $$(k-1)$$ ( k - 1 ) -stable instances of k-terminal cut with isolating cuts

Mark Velednitsky ()
Additional contact information
Mark Velednitsky: University of California

Journal of Combinatorial Optimization, 2022, vol. 43, issue 2, No 1, 297-311

Abstract: Abstract The k-terminal cut problem, also known as the multiterminal cut problem, is defined on an edge-weighted graph with k distinct vertices called “terminals.” The goal is to remove a minimum weight collection of edges from the graph such that there is no path between any pair of terminals. The problem is APX-hard. Isolating cuts are minimum cuts which separate one terminal from the rest. The union of all the isolating cuts, except the largest, is a $$(2-2/k)$$ ( 2 - 2 / k ) -approximation to the optimal k-terminal cut. An instance of k-terminal cut is $$\gamma $$ γ -stable if edges in the cut can be multiplied by up to $$\gamma $$ γ without changing the unique optimal solution. In this paper, we show that, in any $$(k-1)$$ ( k - 1 ) -stable instance of k-terminal cut, the source sets of the isolating cuts are the source sets of the unique optimal solution to that k-terminal cut instance. We conclude that the $$(2-2/k)$$ ( 2 - 2 / k ) -approximation algorithm returns the optimal solution on $$(k-1)$$ ( k - 1 ) -stable instances. Ours is the first result showing that this $$(2-2/k)$$ ( 2 - 2 / k ) -approximation is an exact optimization algorithm on a special class of graphs. We also show that our $$(k-1)$$ ( k - 1 ) -stability result is tight. We construct $$(k-1-\epsilon )$$ ( k - 1 - ϵ ) -stable instances of the k-terminal cut problem which only have trivial isolating cuts: that is, the source set of the isolating cuts for each terminal is just the terminal itself. Thus, the $$(2-2/k)$$ ( 2 - 2 / k ) -approximation does not return an optimal solution.

Keywords: stability; isolating cuts; Approximation; k-terminal cut (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-021-00769-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:43:y:2022:i:2:d:10.1007_s10878-021-00769-3

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-021-00769-3

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().