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

The notion of Turing kernelization investigates whether a polynomial-timealgorithm can solve an NP-hard problem, when it is aided by an oracle that canbe queried for the answers to bounded-size subproblems. One of the main openproblems in this direction is whether k-Path admits a polynomial Turing kernel:can a polynomial-time algorithm determine whether an undirected graph has asimple path of length k, using an oracle that answers queries of size poly(k)?  We show this can be done when the input graph avoids a fixed graph H as atopological minor, thereby significantly generalizing an earlier result forbounded-degree and $K_{3,t}$-minor-free graphs. Moreover, we show that k-Patheven admits a polynomial Turing kernel when the input graph is notH-topological-minor-free itself, but contains a known vertex modulator of sizebounded polynomially in the parameter, whose deletion makes it so. To obtainour results, we build on the graph minors decomposition to show that anyH-topological-minor-free graph that does not contain a k-path, has a separationthat can safely be reduced after communication with the oracle.

Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor