2026-07-20T05:35:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22896 2025-10-02T13:36:48Z ddc:004 open_access

Unfairly Splitting Separable Necklaces Schnider, Patrick Stalder, Linus Weber, Simon Necklace splitting n-separability well-separation Ham Sandwich alpha-Ham Sandwich unfair splitting fair division 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 α-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 α-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 α-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 α-Ham Sandwich. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Patrick Schnider and Linus Stalder and Simon Weber 2025 Is Part Of LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2025.71 urn:nbn:de:0030-drops-228963 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.71 eng https://creativecommons.org/licenses/by/4.0/legalcode