Unfairly Splitting Separable Necklaces
<|reference_start|>Unfairly Splitting Separable Necklaces: The Necklace Splitting problem is a classical problem in combinatorics that has been intensively studied both from a combinatorial and a computational point of view. It is well-known that the Necklace Splitting problem reduces to the discrete Ham Sandwich problem. This reduction was crucial in the proof of PPA-completeness of the Ham Sandwich problem. Recently, Borzechowski, Schnider and Weber [ISAAC'23] introduced a variant of Necklace Splitting that similarly reduces to the $\alpha$-Ham Sandwich problem, which lies in the complexity class UEOPL but is not known to be complete. To make this reduction work, the input necklace is guaranteed to be n-separable. They showed that these necklaces can be fairly split in polynomial time and thus this subproblem cannot be used to prove UEOPL-hardness for $\alpha$-Ham Sandwich. We consider the more general unfair necklace splitting problem on n-separable necklaces, i.e., the problem of splitting these necklaces such that each thief gets a desired fraction of each type of jewels. This more general problem is the natural necklace-splitting-type version of $\alpha$-Ham Sandwich, and its complexity status is one of the main open questions posed by Borzechowski, Schnider and Weber. We show that the unfair splitting problem is also polynomial-time solvable, and can thus also not be used to show UEOPL-hardness for $\alpha$-Ham Sandwich.<|reference_end|>
@article{schnider2024unfairly,
    title={Unfairly Splitting Separable Necklaces},
    author={Patrick Schnider, Linus Stalder, Simon Weber},
    journal={arXiv preprint arXiv:2408.17126},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.17126},
    primaryClass={cs.DS cs.CG}
}