English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

It is well-known that the 2-Thief-Necklace-Splitting problem reduces to thediscrete Ham Sandwich problem. In fact, this reduction was crucial in the proofof the PPA-completeness of the Ham Sandwich problem [Filos-Ratsikas andGoldberg, STOC'19]. Recently, a variant of the Ham Sandwich problem called$\alpha$-Ham Sandwich has been studied, in which the point sets are guaranteedto be well-separated [Steiger and Zhao, DCG'10]. The complexity of this searchproblem remains unknown, but it is known to lie in the complexity class UEOPL[Chiu, Choudhary and Mulzer, ICALP'20]. We define the analogue of thiswell-separability condition in the necklace splitting problem -- a necklace is$n$-separable, if every subset $A$ of the $n$ types of jewels can be separatedfrom the types $[n]\setminus A$ by at most $n$ separator points. By thereduction to the Ham Sandwich problem it follows that this version of necklacesplitting has a unique solution.  We furthermore provide two FPT algorithms: The first FPT algorithm solves2-Thief-Necklace-Splitting on $(n-1+\ell)$-separable necklaces with $n$ typesof jewels and $m$ total jewels in time $2^{O(\ell\log\ell)}+m^2$. Inparticular, this shows that 2-Thief-Necklace-Splitting is polynomial-timesolvable on $n$-separable necklaces. Thus, attempts to show hardness of$\alpha$-Ham Sandwich through reduction from the 2-Thief-Necklace-Splittingproblem cannot work. The second FPT algorithm tests $(n-1+\ell)$-separabilityof 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, eventhough testing well-separation of point sets is coNP-complete [Bergold et al.,SWAT'22].

An FPT Algorithm for Splitting a Necklace Among Two Thieves