Source author record

S. Saurabh

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms

Catalog footprint

Research overview

2works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2012arXiv

Fixed-parameter tractability of satisfying beyond the number of variables

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 $ν(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 $(ν(F)+k)$ -\textsc{SAT}) is fixed-parameter tractable: Given a formula $F$ , decide whether we can satisfy at least $ν(F)+k$ clauses in $F$ , where $k$ is the parameter. A formula $F$ is called variable-matched if $ν(F)=|V(F)|.$ Let $δ(F)=|F|-|V(F)|$ and $δ^*(F)=\max_{F'\subseteq F} δ(F').$ Our main result implies fixed-parameter tractability of {\sc MaxSat} parameterized by $δ(F)$ for variable-matched formulas $F$ ; this complements related results of Kullmann (2000) and Szeider (2004) for {\sc MaxSat} parameterized by $δ^*(F)$ . To obtain our main result, we reduce $(ν(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 $X\subseteq U$ such that $C\cap X\neq \emptyset$ for each $C\in \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).

preprint2012arXiv

Parameterized Study of the Test Cover Problem

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 collection, $\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.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.