Multiobjective Hypergraph Min-Cut in Quasi-Polynomial Time

Abstract

We study the multiobjective hypergraph min-cut problem: Given a hypergraph $H=(V,E)$ and $k$ cost functions $c_1,c_2,\dots ,c_k:E\to {\mathbb{Z}}_{\ge 0}$, the goal is to find a non-empty proper subset $U⊊V$ of vertices with minimum ${\max }_{i\in [k]}{c}_i(\delta (U))$. When $k$ is part of input, the problem is NP-hard (even in graphs). We focus on fixed-constant $k$ setting (e.g., $k=1,2,3,\dots$). Single-objective hypergraph min-cut as well as multiobjective graph min-cut for a constant number of objectives admit polynomial-time algorithms. In contrast to these special cases, the complexity of multiobjective hypergraph min-cut remains open even for $k=2$. Known techniques fail to extend due to structural differences between graphs and hypergraphs. For $k$-objective hypergraph min-cut when $k$ is a fixed constant, we design a randomized PTAS, and two different randomized quasi-polynomial time algorithms. As an application of our $2$-objective hypergraph min-cut results, we obtain a quasi-polynomial time approximation scheme (QPTAS) for hypergraph connectivity interdiction. AI tools were used to iterate and refine the algorithmic ideas underlying this work.