Multiway Cuts with a Choice of Representatives
<|reference_start|>Multiway Cuts with a Choice of Representatives: In this paper, we study 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 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.<|reference_end|>
@article{bérczi2024multiway,
    title={Multiway Cuts with a Choice of Representatives},
    author={Krist'of B'erczi, Tam'as Kir'aly, Daniel P. Szabo},
    journal={arXiv preprint arXiv:2407.03877},
    year={2024},
    doi={10.4230/LIPIcs.MFCS.2024.18},
    archivePrefix={arXiv},
    eprint={2407.03877},
    primaryClass={cs.DS}
}