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 show that Odd Cycle Transversal and Vertex Multiway Cut admitdeterministic polynomial kernels when restricted to planar graphs andparameterized by the solution size. This answers a question of Saurabh. On theway to these results, we provide an efficient sparsification routine in theflavor of the sparsification routine used for the Steiner Tree problem inplanar graphs (FOCS 2014). It differs from the previous work because itpreserves the existence of low-cost subgraphs that are not necessarily Steinertrees in the original plane graph, but structures that turn into (supergraphsof) Steiner trees after adding all edges between pairs of vertices that lie ona common face. We also show connections between Vertex Multiway Cut and theVertex Planarization problem, where the existence of a polynomial kernelremains an important open problem.

A deterministic polynomial kernel for Odd Cycle Transversal and Vertex Multiway Cut in planar graphs