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

A kernelization for a parameterized decision problem $\mathcal{Q}$ is apolynomial-time preprocessing algorithm that reduces any parameterized instance$(x,k)$ into an instance $(x',k')$ whose size is bounded by a function of $k$alone and which has the same yes/no answer for $\mathcal{Q}$. Suchpreprocessing algorithms cannot exist in the context of counting problems, whenthe answer to be preserved is the number of solutions, since this number can bearbitrarily large compared to $k$. However, we show that for counting minimumfeedback vertex sets of size at most $k$, and for counting minimum dominatingsets of size at most $k$ in a planar graph, there is a polynomial-timealgorithm that either outputs the answer or reduces to an instance $(G',k')$ ofsize polynomial in $k$ with the same number of minimum solutions. This showsthat a meaningful theory of kernelization for counting problems is possible andopens the door for future developments. Our algorithms exploit that if thenumber of solutions exceeds $2^{\mathsf{poly}(k)}$, the size of the input isexponential in terms of $k$ so that the running time of a parameterizedcounting algorithm can be bounded by $\mathsf{poly}(n)$. Otherwise, we can usegadgets that slightly increase $k$ to represent choices among $2^{O(k)}$options by only $\mathsf{poly}(k)$ vertices.

Kernelization for Counting Problems on Graphs: Preserving the Number of Minimum Solutions