Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new user(Non-)existence of Polynomial Kernels for the Test Cover Problem
173
0
0.0
(
0
)
Added by
Gregory Gutin
Publication date
2012
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The input of the Test Cover problem consists of a set $V$ of vertices, and a collection ${cal E}={E_1,..., E_m}$ of distinct subsets of $V$, called tests. A test $E_q$ separates a pair $v_i,v_j$ of vertices if $|{v_i,v_j}cap E_q|=1.$ A subcollection ${cal T}subseteq {cal E}$ is a test cover if each pair $v_i,v_j$ of distinct vertices is separated by a test in ${cal T}$. The objective is to find a test cover of minimum cardinality, if one exists. This problem 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) decide whether there is a test cover with at most $|V|-k$ tests. Both parameterizations are known to be fixed-parameter tractable. We prove that none have a polynomial size kernel unless $NPsubseteq coNP/poly$. Our proofs use the cross-composition method recently introduced by Bodlaender et al. (2011) and parametric duality introduced by Chen et al. (2005). The result for the parameterization (a) was an open problem (private communications with Henning Fernau 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-bounded by a constant.
rate research
Read More
Finding cliques in random graphs and the closely related planted clique variant, where a clique of size t is planted in a random G(n,1/2) graph, have been the focus of substantial study in algorithm design. Despite much effort, the best known polynomial-time algorithms only solve the problem for t = Theta(sqrt(n)). Here we show that beating sqrt(n) would require substantially new algorithmic ideas, by proving a lower bound for the problem in the sum-of-squares (or Lasserre) hierarchy, the most powerful class of semi-definite programming algorithms we know of: r rounds of the sum-of-squares hierarchy can only solve the planted clique for t > sqrt(n)/(C log n)^(r^2). Previously, no nontrivial lower bounds were known. Our proof is formulated as a degree lower bound in the Positivstellensatz algebraic proof system, which is equivalent to the sum-of-squares hierarchy. The heart of our (average-case) lower bound is a proof that a certain random matrix derived from the input graph is (with high probability) positive semidefinite. Two ingredients play an important role in this proof. The first is the classical theory of association schemes, applied to the average and variance of that random matrix. The second is a new large deviation inequality for matrix-valued polynomials. Our new tail estimate seems to be of independent interest and may find other applications, as it generalizes both the estimates on real-valued polynomials and on sums of independent random matrices.
Threshold graphs are a class of graphs that have many equivalent definitions and have applications in integer programming and set packing problems. A graph is said to have a threshold cover of size $k$ if its edges can be covered using $k$ threshold graphs. Chvatal and Hammer, in 1977, defined the threshold dimension $mathrm{th}(G)$ of a graph $G$ to be the least integer $k$ such that $G$ has a threshold cover of size $k$ and observed that $mathrm{th}(G)geqchi(G^*)$, where $G^*$ is a suitably constructed auxiliary graph. Raschle and Simon~[Proceedings of the Twenty-seventh Annual ACM Symposium on Theory of Computing, STOC 95, pages 650--661, 1995] proved that $mathrm{th}(G)=chi(G^*)$ whenever $G^*$ is bipartite. We show how the lexicographic method of Hell and Huang can be used to obtain a completely new and, we believe, simpler proof for this result. For the case when $G$ is a split graph, our method yields a proof that is much shorter than the ones known in the literature.
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.
The hypergraph duality problem DUAL is defined as follows: given two simple hypergraphs $mathcal{G}$ and $mathcal{H}$, decide whether $mathcal{H}$ consists precisely of all minimal transversals of $mathcal{G}$ (in which case we say that $mathcal{G}$ is the dual of $mathcal{H}$). This problem is equivalent to deciding whether two given non-redundant monotone DNFs are dual. It is known that non-DUAL, the complementary problem to DUAL, is in $mathrm{GC}(log^2 n,mathrm{PTIME})$, where $mathrm{GC}(f(n),mathcal{C})$ denotes the complexity class of all problems that after a nondeterministic guess of $O(f(n))$ bits can be decided (checked) within complexity class $mathcal{C}$. It was conjectured that non-DUAL is in $mathrm{GC}(log^2 n,mathrm{LOGSPACE})$. In this paper we prove this conjecture and actually place the non-DUAL problem into the complexity class $mathrm{GC}(log^2 n,mathrm{TC}^0)$ which is a subclass of $mathrm{GC}(log^2 n,mathrm{LOGSPACE})$. We here refer to the logtime-uniform version of $mathrm{TC}^0$, which corresponds to $mathrm{FO(COUNT)}$, i.e., first order logic augmented by counting quantifiers. We achieve the latter bound in two steps. First, based on existing problem decomposition methods, we develop a new nondeterministic algorithm for non-DUAL that requires to guess $O(log^2 n)$ bits. We then proceed by a logical analysis of this algorithm, allowing us to formulate its deterministic part in $mathrm{FO(COUNT)}$. From this result, by the well known inclusion $mathrm{TC}^0subseteqmathrm{LOGSPACE}$, it follows that DUAL belongs also to $mathrm{DSPACE}[log^2 n]$. Finally, by exploiting the principles on which the proposed nondeterministic algorithm is based, we devise a deterministic algorithm that, given two hypergraphs $mathcal{G}$ and $mathcal{H}$, computes in quadratic logspace a transversal of $mathcal{G}$ missing in $mathcal{H}$.
Given a graph $G=(V,E)$ and a positive integer $tgeq2$, the task in the vertex cover $P_t$ ($VCP_t$) problem is to find a minimum subset of vertices $Fsubseteq V$ such that every path of order $t$ in $G$ contains at least one vertex from $F$. The $VCP_t$ problem is NP-complete for any integer $tgeq2$ and has many applications in real world. Recently, the authors presented a dynamic programming algorithm running in time $4^pcdot n^{O(1)}$ for the $VCP_3$ problem on $n$-vertex graphs with treewidth $p$. In this paper, we propose an improvement of it and improved the time-complexity to $3^pcdot n^{O(1)}$. The connected vertex cover $P_3$ ($CVCP_3$) problem is the connected variation of the $VCP_3$ problem where $G[F]$ is required to be connected. Using the Cut&Count technique, we give a randomized algorithm with runtime $4^pcdot n^{O(1)}$ for the $CVCP_3$ problem on $n$-vertex graphs with treewidth $p$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
