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

In a (parameterized) graph edge modification problem, we are given a graph$G$, an integer $k$ and a (usually well-structured) class of graphs$\mathcal{G}$, and ask whether it is possible to transform $G$ into a graph $G'\in \mathcal{G}$ by adding and/or removing at most $k$ edges. Parameterizedgraph edge modification problems received considerable attention in the lastdecades.  In this paper, we focus on finding small kernels for edge modificationproblems. One of the most studied problems is the Cluster Editing problem, inwhich the goal is to partition the vertex set into a disjoint union of cliques.Even if this problem admits a $2k$ kernel [Cao, 2012], this kernel does notreduce the size of most instances. Therefore, we explore the question ofwhether linear kernels are a theoretical limit in edge modification problems,in particular when the target graphs are very structured (such as a partitioninto cliques for instance). We prove, as far as we know, the first sublinearkernel for an edge modification problem. Namely, we show that Clique +Independent Set Deletion, which is a restriction of Cluster Deletion, admits akernel of size $O(k/\log k)$.  We also obtain small kernels for several other edge modification problems. Weprove that Split Addition (and the equivalent Split Deletion) admits a linearkernel, improving the existing quadratic kernel of Ghosh et al. [Ghosh et al.,2015]. We complement this result by proving that Trivially Perfect Additionadmits a quadratic kernel (improving the cubic kernel of Guo [Guo, 2007]), andfinally prove that its triangle-free version (Starforest Deletion) admits alinear kernel, which is optimal under ETH.

(Sub)linear kernels for edge modification problems towards structured graph classes