Mimicking Networks for Constrained Multicuts in Hypergraphs
<|reference_start|>Mimicking Networks for Constrained Multicuts in Hypergraphs: In this paper, we study a \emph{multicut-mimicking network} for a hypergraph over terminals $T$ with a parameter $c$. It is a hypergraph preserving the minimum multicut values of any set of pairs over $T$ where the value is at most $c$. This is a new variant of the multicut-mimicking network of a graph in [Wahlstr\"om ICALP'20], which introduces a parameter $c$ and extends it to handle hypergraphs. Additionally, it is a natural extension of the \emph{connectivity-$c$ mimicking network} introduced by [Chalermsook et al. SODA'21] and [Jiang et al. ESA'22] that is a (hyper)graph preserving the minimum cut values between two subsets of terminals where the value is at most $c$. We propose an algorithm for a hypergraph that returns a multicut-mimicking network over terminals $T$ with a parameter $c$ having $|T|c^{O(r\log c)}$ hyperedges in $p^{1+o(1)}+|T|(c^r\log n)^{\tilde{O}(rc)}m$ time, where $p$ and $r$ are the total size and the rank, respectively, of the hypergraph.<|reference_end|>
@article{cho2024mimicking,
    title={Mimicking Networks for Constrained Multicuts in Hypergraphs},
    author={Kyungjin Cho and Eunjin Oh},
    journal={arXiv preprint arXiv:2409.12548},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.12548},
    primaryClass={cs.DS}
}