Improved Hardness Results of the Cardinality-Based Minimum s-t Cut Problem in Hypergraphs
<|reference_start|>Improved Hardness Results of the Cardinality-Based Minimum s-t Cut Problem in Hypergraphs: In hypergraphs an edge that crosses a cut can be split in several ways, depending on how many nodes are placed on each side of the cut. A cardinality-based splitting function assigns a nonnegative cost of $w_i$ for each cut hyperedge $e$ with exactly $i$ nodes on the side of the cut that contains the minority of nodes from $e$. The cardinality-based minimum $s$-$t$ cut aims to find an $s$-$t$ cut with minimum total cost. Assuming the costs $w_i$ are polynomially bounded by the input size and $w_0=0$ and $w_1=1$, we show that the problem becomes NP-hard outside the submodular region found by Veldt et al. Our result also holds for $k$-uniform hypergraphs with $k \geq 4$. Specifically for $4$-uniform hypergraphs we show that the problem is NP-hard for all $w_2>2$, and additionally prove that the \textsc{No-Even-Split} problem is NP-hard.<|reference_end|>
@article{adriaens2024improved,
    title={Improved Hardness Results of the Cardinality-Based Minimum s-t Cut
  Problem in Hypergraphs},
    author={Florian Adriaens and Iiro Kumpulainen and Nikolaj Tatti},
    journal={arXiv preprint arXiv:2409.07201},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.07201},
    primaryClass={cs.CC cs.DS}
}