2026-07-26T00:11:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20581 2024-08-23T05:50:28Z ddc:004 open_access

Multiway Cuts with a Choice of Representatives Bérczi, Kristóf Király, Tamás Szabo, Daniel P. Approximation algorithms Multiway cut CKR relaxation Steiner multicut In the Multiway Cut problem, we are given an undirected graph with nonnegative edge weights and a subset of k terminals, and the goal is to determine a set of edges of minimum total weight whose removal disconnects each terminal from the rest. The problem is APX-hard for k ≥ 3, and an extensive line of research has concentrated on closing the gap between the best upper and lower bounds for approximability and inapproximability, respectively. In this paper, we study several generalizations of Multiway Cut where the terminals can be chosen as representatives from sets of candidates T₁,…,T_q. In this setting, one is allowed to choose these representatives so that the minimum-weight cut separating these sets via their representatives is as small as possible. We distinguish different cases depending on (A) whether the representative of a candidate set has to be separated from the other candidate sets completely or only from the representatives, and (B) whether there is a single representative for each candidate set or the choice of representative is independent for each pair of candidate sets. For fixed q, we give approximation algorithms for each of these problems that match the best known approximation guarantee for Multiway Cut. Our technical contribution is a new extension of the CKR relaxation that preserves approximation guarantees. For general q, we show o(log q)-inapproximability for all cases where the choice of representatives may depend on the pair of candidate sets, as well as for the case where the goal is to separate a fixed node from a single representative from each candidate set. As a positive result, we give a 2-approximation algorithm for the case where we need to choose a single representative from each candidate set. This is a generalization of the (2-2/k)-approximation for k-Cut, and we can solve it by relating the tree case to optimization over a gammoid. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kristóf Bérczi and Tamás Király and Daniel P. Szabo 2024 Is Part Of LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2024.25 urn:nbn:de:0030-drops-205813 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.25 eng https://creativecommons.org/licenses/by/4.0/legalcode