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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We study the following two fixed-cardinality optimization problems (amaximization and a minimization variant). For a fixed $\alpha$ between zero andone we are given a graph and two numbers $k \in \mathbb{N}$ and $t \in\mathbb{Q}$. The task is to find a vertex subset $S$ of exactly $k$ verticesthat has value at least (resp. at most for minimization) $t$. Here, the valueof a vertex set computes as $\alpha$ times the number of edges with exactly oneendpoint in $S$ plus $1-\alpha$ times the number of edges with both endpointsin $S$. These two problems generalize many prominent graph problems, such asDensest $k$-Subgraph, Sparsest $k$-Subgraph, Partial Vertex Cover, and Max($k$,$n-k$)-Cut.  In this work, we complete the picture of their parameterized complexity onseveral types of sparse graphs that are described by structural parameters. Inparticular, we provide kernelization algorithms and kernel lower bounds forthese problems. A somewhat surprising consequence of our kernelizations is thatPartial Vertex Cover and Max $(k,n-k)$-Cut not only behave in the same way butthat the kernels for both problems can be obtained by the same algorithms.

Covering Many (or Few) Edges with k Vertices in Sparse Graphs