|
In the Multiway Cut problem, we are given an undirected graph with non-negative 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\geq 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 introduce several generalizations of Multiway Cut where the terminals can be chosen as \emph{representatives} from sets of \emph{candidates} $T_1,\ldots,T_q$.
In this setting, one is allowed to choose these representatives so that the minimum-weight cut separating these sets \emph{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 whether the choice of representative is independent for each pair of candidate sets.
For fixed $q$, we give approximations for each of these problems that match the best known approximation bounds for Multiway Cut. For general $q$, we show $o(\log q)$-inapproximability for all of the cases where the choice of representatives may depend on the pair of candidate sets, as well as for the case where we separate a fixed node from a single representative from each candidate set. Furthermore, we give $2$-approximation algorithms when we must choose a single representative from each candidate set for two cases: when the goal is to separate them from each other, and when each representative must be separated from the other candidate sets completely.
Bibtex entry:
| AUTHOR | = | {B{\'e}rczi, Krist{\'o}f and Kir{\'a}ly, Tam{\'a}s and Szabo Peter, Daniel}, |
| TITLE | = | { Multiway Cuts with a Choice of Representatives}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2023}, |
| NUMBER | = | {TR-2023-19} |