Mimicking Networks for Constrained Multicuts in Hypergraphs

2024/09/19 by Cho, Kyungjin, Oh, Eunjin
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2409.12548

Abstract

In this paper, we study a 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öm ICALP'20], which introduces a parameter c and extends it to handle hypergraphs. Additionally, it is a natural extension of the 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(rlog c)} hyperedges in p^1+o(1)+|T|(c^rlog n)^O(rc)m time, where p and r are the total size and the rank, respectively, of the hypergraph.

Related

• Mimicking Networks Parameterized by Connectivity
• Quasipolynomial multicut-mimicking networks and kernelization of\n multiway cut problems
• On Mimicking Networks Representing Minimum Terminal Cuts
• Mimicking Networks and Succinct Representations of Terminal Cuts
• An exponential lower bound for cut sparsifiers in planar graphs