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

We present an algorithm for the extensively studied Long Path and Long Cycleproblems on unit disk graphs that runs in time $2^{O(\sqrt{k})}(n+m)$. Underthe Exponential Time Hypothesis, Long Path and Long Cycle on unit disk graphscannot be solved in time $2^{o(\sqrt{k})}(n+m)^{O(1)}$ [de Berg et al., STOC2018], hence our algorithm is optimal. Besides the$2^{O(\sqrt{k})}(n+m)^{O(1)}$-time algorithm for the (arguably) much simplerVertex Cover problem by de Berg et al. [STOC 2018] (which easily follows fromthe existence of a $2k$-vertex kernel for the problem), this is the only knownETH-optimal fixed-parameter tractable algorithm on UDGs. Previously, Long Pathand Long Cycle on unit disk graphs were only known to be solvable in time$2^{O(\sqrt{k}\log k)}(n+m)$. This algorithm involved the introduction of a newtype of a tree decomposition, entailing the design of a very tedious dynamicprogramming procedure. Our algorithm is substantially simpler: we completelyavoid the use of this new type of tree decomposition. Instead, we use a markingprocedure to reduce the problem to (a weighted version of) itself on a standardtree decomposition of width $O(\sqrt{k})$.

ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs