Open access
Date
2023-12Type
- Conference Paper
ETH Bibliography
yes
Altmetrics
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 α-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-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] \ A by at most n separator points. Since this version of necklace splitting reduces to α-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 + ℓ)-separable necklaces with n types of jewels and m total jewels in time 2^O(ℓ log ℓ) + O(m²). In particular, this shows that 2-Thief-Necklace-Splitting is polynomial-time solvable on n-separable necklaces. Thus, attempts to show hardness of α-Ham Sandwich through reduction from the 2-Thief-Necklace-Splitting problem cannot work. The second FPT algorithm tests (n − 1 + ℓ)-separability of a given necklace with n types of jewels in time 2O(ℓ²) · n⁴. In particular, n-separability can thus be tested in polynomial time, even though testing well-separation of point sets is co-NP-complete [Bergold et al., SWAT’22]. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000647850Publication status
publishedExternal links
Book title
34th International Symposium on Algorithms and Computation (ISAAC 2023)Journal / series
Leibniz International Proceedings in Informatics (LIPIcs)Volume
Pages / Article No.
Publisher
Dagstuhl PublishingEvent
Subject
Necklace splitting; n-separability; well-separation; ham sandwich; FPTOrganisational unit
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)
Funding
204320 - Unique Sink Orientations (SNF)
More
Show all metadata
ETH Bibliography
yes
Altmetrics