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

The input of the Test Cover problem consists of a set $V$ of vertices, and acollection ${\cal E}=\{E_1,..., E_m\}$ of distinct subsets of $V$, calledtests. A test $E_q$ separates a pair $v_i,v_j$ of vertices if $|\{v_i,v_j\}\capE_q|=1.$ A subcollection ${\cal T}\subseteq {\cal E}$ is a test cover if eachpair $v_i,v_j$ of distinct vertices is separated by a test in ${\cal T}$. Theobjective is to find a test cover of minimum cardinality, if one exists. Thisproblem is NP-hard.  We consider two parameterizations the Test Cover problem with parameter $k$:(a) decide whether there is a test cover with at most $k$ tests, (b) decidewhether there is a test cover with at most $|V|-k$ tests. Bothparameterizations are known to be fixed-parameter tractable. We prove that nonehave a polynomial size kernel unless $NP\subseteq coNP/poly$. Our proofs usethe cross-composition method recently introduced by Bodlaender et al. (2011)and parametric duality introduced by Chen et al. (2005). The result for theparameterization (a) was an open problem (private communications with HenningFernau and Jiong Guo, Jan.-Feb. 2012). We also show that the parameterization(a) admits a polynomial size kernel if the size of each test is upper-boundedby a constant.

(Non-)existence of Polynomial Kernels for the Test Cover Problem