Search

Most optimization problems are notoriously hard. Considerable efforts must be spent in obtaining an optimal solution to certain instances that we encounter in the real world scenarios. Often it turns out that input instances get modified locally in some small ways due to changes in the application world. The natural question here is, given an optimal solution for an old instance $I_O$, can we construct an optimal solution for the new instance $I_N$, where $I_N$ is the instance $I_O$ with some local modifications. Reoptimization of NP-hard optimization problem precisely addresses this concern. It turns out that for some reoptimization versions of the NP-hard problems, we may only hope to obtain an approximate solution to a new instance. In this paper, we specifically address the reoptimization of path vertex cover problem. The objective in $k$-$path$ vertex cover problem is to compute a minimum subset $S$ of the vertices in a graph $G$ such that after removal of $S$ from $G$ there is no path with $k$ vertices in the graph. We show that when a constant number of vertices are inserted, reoptimizing unweighted $k$-$path$ vertex cover problem admits a PTAS. For weighted $3$-$path$ vertex cover problem, we show that when a constant number of vertices are inserted, the reoptimization algorithm achieves an approximation factor of $1.5$, hence an improvement from known $2$-approximation algorithm for the optimization version. We provide reoptimization algorithm for weighted $k$-$path$ vertex cover problem $(k \geq 4)$ on bounded degree graphs, which is also an NP-hard problem. Given a $\rho$-approximation algorithm for $k$-$path$ vertex cover problem on bounded degree graphs, we show that it can be reoptimized within an approximation factor of $(2-\frac{1}{\rho})$ under constant number of vertex insertions.

We consider a variant of socially stable marriage problem where preference lists may be incomplete, may contain ties and may have bounded length. In real world application like NRMP and Scottish medical matching scheme such restrictions arise very frequently where set of agents (man/woman) is very large and providing a complete and strict order preference list is practically in-feasible. In presence of ties in preference lists, the most common solution is weakly socially stable matching. It is a fact that in an instance, weakly stable matching can have different sizes. This motivates the problem of finding a maximum cardinality weakly socially stable matching., Comment: This paper has been withdrawn by the author due to a change in algorithm

Hamiltonicity is an important property in parallel and distributed computation. Existence of Hamiltonian cycle allows efficient emulation of distributed algorithms on a network wherever such algorithm exists for linear-array and ring, and can ensure deadlock freedom in some routing algorithms in hierarchical interconnection networks. Hamiltonicity can also be used for construction of independent spanning tree and leads to designing fault tolerant protocols. Optical Transpose Interconnection Systems or OTIS (also referred to as two-level swapped network) is a widely studied interconnection network topology which is popular due to high degree of scalability, regularity, modularity and package ability. Surprisingly, to our knowledge, only one strong result is known regarding Hamiltonicity of OTIS - showing that OTIS graph built of Hamiltonian base graphs are Hamiltonian. In this work we consider Hamiltonicity of OTIS networks, built on Non-Hamiltonian base and answer some important questions. First, we prove that Hamiltonicity of base graph is not a necessary condition for the OTIS to be Hamiltonian. We present an infinite family of Hamiltonian OTIS graphs composed on Non-Hamiltonian base graphs. We further show that, it is not sufficient for the base graph to have Hamiltonian path for the OTIS constructed on it to be Hamiltonian. We give constructive proof of Hamiltonicity for a large family of Butterfly-OTIS. This proof leads to an alternate efficient algorithm for independent spanning trees construction on this class of OTIS graphs. Our algorithm is linear in the number of vertices as opposed to the generalized algorithm, which is linear in the number of edges of the graph.

In this paper, we present a very important primitive called Information Checking Protocol (ICP) which plays an important role in constructing statistical Verifiable Secret Sharing (VSS) and Weak Secret Sharing (WSS) protocols. Informally, ICP is a tool for authenticating messages in the presence of computationally unbounded corrupted parties. Here we extend the basic bare-bone definition of ICP, introduced by Rabin et al. and then present an ICP that attains the best communication complexity and round complexity among all the existing ICPs in the literature. We also show that our ICP satisfies several interesting properties such as linearity property which is an important requirement in many applications of ICP. Though not presented in this paper, we can design communication and round efficient statistical (i.e involves negligible error probability in computation) VSS and Multiparty Computation (MPC) protocol using our new ICP.

In this paper, we prove that the power of simple H systems of the $(2,3)$ type with permitting contexts and target alphabet is equal to extended H systems with permitting contexts and radius of the rules equal to one. We also prove interesting results on simple extended H systems and extended H systems with forbidden contexts., Journal of Automata, Languages and Combinatorics, Volume 5, Number 4, 2000, 457-473