An FPT Algorithm for Splitting a Necklace Among Two Thieves

MaRDI QIDQ6441476zbMATH OpenFDO

Authors Michaela Borzechowski, Patrick Schnider, Simon Weber

Publication date 26 June 2023

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 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 UEOPL [Chiu, Choudhary and Mulzer, ICALP'20]. We define the analogue of this well-separability 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]setminusA$ by at most $n$ separator points. By the reduction to the Ham Sandwich problem it follows that this version of necklace splitting has a unique solution. 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(elllogell)}+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(el{l}^2)}cdot{n}^4$. In particular, $n$-separability can thus be tested in polynomial time, even though testing well-separation of point sets is coNP-complete [Bergold et al., SWAT'22].

This page was built for publication: An FPT Algorithm for Splitting a Necklace Among Two Thieves

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6441476)