Minimum k-way cut in a hypergraph

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Let $H=(V,\mathcal E)$ be a finite hypergraph, whose explicitly listed hyperedges may have arbitrary size. Each edge $e$ has a nonnegative binary-encoded rational capacity $c(e)$. Fix an integer $k\ge2$ with $k\le|V|$. A $k$-way cut is a partition $V=V_1\dot\cup\cdots\dot\cup V_k$ into nonempty parts; its cut set consists of the edges meeting at least two distinct parts. Its capacity is $\sum_{e\text{ crossing}}c(e)$, charging a crossing hyperedge once regardless of how many parts it meets. Equivalently, remove minimum-capacity hyperedges so that at least $k$ connected components remain.

Statement recorded in the supplied source.

For every fixed $k$, can a minimum-capacity $k$-way hypergraph cut be found in time polynomial in the encoded input size, with no bound on edge rank? [S2] The historically registered question is answered affirmatively by Theorem 1.1 and the cost extension in Section 1.1 of [S2].

Short English statement

Can a cheapest k-way cut of an arbitrary capacitated hypergraph be computed in polynomial time when k is fixed?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3000056 (AMR-029-0056). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 K. Chandrasekaran and C. Chekuri, Hypergraph k-cut for fixed k in deterministic polynomial time (2020), Introduction, formal Hypergraph-k-Cut definition, Theorem 1.1 and Section 1.1, pp.1--3. https://arxiv.org/pdf/2009.12442.