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/

Zendy Plus

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

Zendy Tools

Zendy Open

We study the concept of \emph{compactor}, which may be seen as acounting-analogue of kernelization in counting parameterized complexity. For afunction $F:\Sigma^*\to \Bbb{N}$ and a parameterization $\kappa: \Sigma^*\to\Bbb{N}$, a compactor $({\sf P},{\sf M})$ consists of a polynomial-timecomputable function ${\sf P}$, called \emph{condenser}, and a computablefunction ${\sf M}$, called \emph{extractor}, such that $F={\sf M}\circ {\sfP}$, and the condensing ${\sf P}(x)$ of $x$ has length at most $s(\kappa(x))$,for any input $x\in \Sigma^*.$ If $s$ is a polynomial function, then thecompactor is said to be of polynomial-size. Although the study oncounting-analogue of kernelization is not unprecedented, it has received littleattention so far. We study a family of vertex-certified counting problems ongraphs that are MSOL-expressible; that is, for an MSOL-formula $\phi$ with onefree set variable to be interpreted as a vertex subset, we want to count all$A\subseteq V(G)$ where $|A|=k$ and $(G,A)\models \phi.$ In this paper, weprove that every vertex-certified counting problems on graphs that is\emph{MSOL-expressible} and \emph{treewidth modulable}, when parameterized by$k$, admits a polynomial-size compactor on $H$-topological-minor-free graphswith condensing time $O(k^2n^2)$ and decoding time $2^{O(k)}.$ This implies theexistence of an {\sf FPT}-algorithm of running time $O(n^2k^2)+2^{O(k)}.$ Allaforementioned complexities are under the Uniform Cost Measure (UCM) modelwhere numbers can be stored in constant space and arithmetic operations can bedone in constant time.

Data-compression for Parametrized Counting Problems on Sparse graphs