We carry out a systematic study of a natural covering problem, used for identification across several areas, in the realm of parameterized complexity. In the {sc Test Cover} problem we are given a set $[n]={1,...,n}$ of items together with a collecti
on, $cal T$, of distinct subsets of these items called tests. We assume that $cal T$ is a test cover, i.e., for each pair of items there is a test in $cal T$ containing exactly one of these items. The objective is to find a minimum size subcollection of $cal T$, which is still a test cover. The generic parameterized version of {sc Test Cover} is denoted by $p(k,n,|{cal T}|)$-{sc Test Cover}. Here, we are given $([n],cal{T})$ and a positive integer parameter $k$ as input and the objective is to decide whether there is a test cover of size at most $p(k,n,|{cal T}|)$. We study four parameterizations for {sc Test Cover} and obtain the following: (a) $k$-{sc Test Cover}, and $(n-k)$-{sc Test Cover} are fixed-parameter tractable (FPT). (b) $(|{cal T}|-k)$-{sc Test Cover} and $(log n+k)$-{sc Test Cover} are W[1]-hard. Thus, it is unlikely that these problems are FPT.
We consider a CNF formula $F$ as a multiset of clauses: $F={c_1,..., c_m}$. The set of variables of $F$ will be denoted by $V(F)$. Let $B_F$ denote the bipartite graph with partite sets $V(F)$ and $F$ and with an edge between $v in V(F)$ and $c in F$
if $v in c$ or $bar{v} in c$. The matching number $ u(F)$ of $F$ is the size of a maximum matching in $B_F$. In our main result, we prove that the following parameterization of {sc MaxSat} (denoted by $( u(F)+k)$-textsc{SAT}) is fixed-parameter tractable: Given a formula $F$, decide whether we can satisfy at least $ u(F)+k$ clauses in $F$, where $k$ is the parameter. A formula $F$ is called variable-matched if $ u(F)=|V(F)|.$ Let $delta(F)=|F|-|V(F)|$ and $delta^*(F)=max_{Fsubseteq F} delta(F).$ Our main result implies fixed-parameter tractability of {sc MaxSat} parameterized by $delta(F)$ for variable-matched formulas $F$; this complements related results of Kullmann (2000) and Szeider (2004) for {sc MaxSat} parameterized by $delta^*(F)$. To obtain our main result, we reduce $( u(F)+k)$-textsc{SAT} into the following parameterization of the {sc Hitting Set} problem (denoted by $(m-k)$-{sc Hitting Set}): given a collection $cal C$ of $m$ subsets of a ground set $U$ of $n$ elements, decide whether there is $Xsubseteq U$ such that $Ccap X eq emptyset$ for each $Cin cal C$ and $|X|le m-k,$ where $k$ is the parameter. Gutin, Jones and Yeo (2011) proved that $(m-k)$-{sc Hitting Set} is fixed-parameter tractable by obtaining an exponential kernel for the problem. We obtain two algorithms for $(m-k)$-{sc Hitting Set}: a deterministic algorithm of runtime $O((2e)^{2k+O(log^2 k)} (m+n)^{O(1)})$ and a randomized algorithm of expected runtime $O(8^{k+O(sqrt{k})} (m+n)^{O(1)})$. Our deterministic algorithm improves an algorithm that follows from the kernelization result of Gutin, Jones and Yeo (2011).
