An FPT Algorithm for Splitting a Necklace Among Two Thieves

Abstract It is well-known that the 2-Thief-Necklace-Splitting problem reduces to the discrete Ham Sandwich problem. In fact, this reduction was crucial in the proof of the $$\textsf{PPA}$$ -completeness of the Ham Sandwich problem [Filos-Ratsikas and Goldberg, STOC’19]. Recently, a variant of the Ham Sandwich problem called $$\alpha $$ -Ham Sandwich has been studied, in which the point sets are guaranteed to be well-separated [Steiger and Zhao, DCG’10]. The complexity of this search problem remains unknown, but it is known to lie in the complexity class $$\textsf{UEOPL}$$ [Chiu, Choudhary and Mulzer, ICALP’20]. We define the analogue of this well-separation condition in the necklace splitting problem — a necklace is n - separable , if every subset A of the n types of jewels can be separated from the types $$[n]\setminus A$$ by at most n separator points. Since this version of necklace splitting reduces to $$\alpha $$ -Ham Sandwich in a solution-preserving way it follows that instances of this version always have unique solutions. We furthermore provide two FPT algorithms: The first FPT algorithm solves 2-Thief-Necklace-Splitting on $$(n-1+\ell )$$ -separable necklaces with n types of jewels and m total jewels in time $$2^{O(\ell \log \ell )}+O(m^2)$$ . In particular, this shows that 2-Thief-Necklace-Splitting is polynomial-time solvable on n -separable necklaces. Thus, attempts to show hardness of $$\alpha $$ -Ham Sandwich through reduction from the 2-Thief-Necklace-Splitting problem cannot work. The second FPT algorithm tests $$(n-1+\ell )$$ -separability of a given necklace with n types of jewels in time $$2^{O(\ell ^2)}\cdot n^4$$ . In particular, n -separability can thus be tested in polynomial time, even though testing well-separation of point sets is $$\textsf{coNP}$$ -complete [Bergold et al., SWAT’22].