Search

In the weighted partial vertex cover problem (WPVC), we are given a graph $G=(V,E)$, cost function $c:V\rightarrow N$, profit function $p:E\rightarrow N$, and positive integers $R$ and $L$. The goal is to check whether there is a subset $V'\subseteq V$ of cost at most $R$, such that the total profit of edges covered by $V'$ is at least $L$. In this paper we study the fixed-parameter tractability of WPVC in bipartite graphs (WPVCB). By extending the methods of Amini et al., we show that WPVCB is FPT with respect to $R$ if $c\equiv 1$. On the negative side, it is $W[1]$-hard for arbitrary $c$, even when $p\equiv 1$. In particular, WPVCB is $W[1]$-hard parameterized by $R$. We complement this negative result by proving that for bounded-degree graphs WPVC is FPT with respect to $R$. The same result holds for the case of WPVCB when we allow to take only one fractional vertex. Additionally, we show that WPVC is FPT with respect to $L$. Finally, we discuss a variant of PVCB in which the edges covered are constrained to include a matching of prescribed size and derive a paramterized algorithm for the same., Comment: 12 pages, no figures

In this paper, we analyze 2CNF formulas from the perspectives of Read-Once resolution (ROR) refutation schemes. We focus on two types of ROR refutations, viz., variable-once refutation and clause-once refutation. In the former, each variable may be used at most once in the derivation of a refutation, while in the latter, each clause may be used at most once. We show that the problem of checking whether a given 2CNF formula has an ROR refutation under both schemes is NP-complete. This is surprising in light of the fact that there exist polynomial refutation schemes (tree-resolution and DAG-resolution) for 2CNF formulas. On the positive side, we show that 2CNF formulas have copy-complexity 2, which means that any unsatisfiable 2CNF formula has a refutation in which any clause needs to be used at most twice., Comment: 14 pages, 3 figures

The Shoshan-Zwick algorithm solves the all pairs shortest paths problem in undirected graphs with integer edge costs in the range $\{1, 2, \dots, M\}$. It runs in $\tilde{O}(M\cdot n^{\omega})$ time, where $n$ is the number of vertices, $M$ is the largest integer edge cost, and $\omega < 2.3727$ is the exponent of matrix multiplication. It is the fastest known algorithm for this problem. This paper points out the erroneous behavior of the Shoshan-Zwick algorithm and revises the algorithm to resolve the issues that cause this behavior. Moreover, it discusses implementation aspects of the Shoshan-Zwick algorithm using currently-existing sub-cubic matrix multiplication algorithms., Comment: 16 pages

The modern integrated circuit is one of the most complex products that has been engineered to-date. It continues to grow in complexity as the years progress. As a result, very large-scale integrated (VLSI) circuit design now involves massive design teams employing state-of-the art computer-aided design (CAD) tools. One of the oldest, yet most important CAD problems for VLSI circuits is physical design automation, where one needs to compute the best physical layout of millions to billions of circuit components on a tiny silicon surface \cite{Lim08}. The process of mapping an electronic design to a chip involves a number of physical design stages, one of which is clustering. In this paper, we focus on problems in clustering which are critical for more sustainable chips. The clustering problem in combinatorial circuits alone is a source of multiple models. In particular, we consider the problem of clustering combinatorial circuits for delay minimization, when logic replication is not allowed ({\sc CN}). The problem of delay minimization when logic replication is allowed ({\sc CA}) has been well studied, and is known to be solvable in polynomial-time \cite{Wong1}. However, unbounded logic replication can be quite expensive. Thus, {\sc CN} is an important problem. We show that selected variants of {\sc CN} are {\bf NP-hard}. We also obtain approximability and inapproximability results for these problems. A preliminary version of this paper appeared in \cite{Don15}., Comment: 20 pages, 10 figures

It is well-known that the Vertex Cover problem is in P on bipartite graphs, however; the computational complexity of the Partial Vertex Cover problem on bipartite graphs is open. In this paper, we first show that the Partial Vertex Cover problem is NP-hard on bipartite graphs. We then identify an interesting special case of bipartite graphs, for which the Partial Vertex Cover problem can be solved in polynomial-time. We also show that the set of acyclic bipartite graphs, i.e., forests, and the set of bipartite graph where the degree of each vertex is at most 3 fall into that special case. Therefore, we prove that the Partial Vertex Cover problem is in P on trees, and it is also in P on the set of bipartite graphs where the degree of each vertex is at most 3., Comment: 11 pages, 4 figures