Strictly Unfriendly $k$-Partitions: Sharp Degree Thresholds and ETH-Based Lower Bounds

Sanjay Jain, Frank Stephan, Haoyun Tang

We present a complete complexity classification and fine-grained analysis for the Strictly Unfriendly $k$-Partition problem ($\text{SU}k\text{P}$), which asks whether the vertices…