Sudeshna Kolay

Palash Dey, Anubhav Dhar, Ashlesha Hota et al.

In this paper, we study the Maximum Common Vertex Subgraph problem: Given two input graphs $G_1,G_2$ and a non-negative integer $h$, is there a common subgraph $H$ on at least $h$ vertices such that there is no isolated vertex in $H$. In other words, each connected component of $H$ has at least $2$ vertices. This problem naturally arises in graph theory along with other variants of the well-studied Maximum Common Subgraph problem and also has applications in computational social choice. We show that this problem is NP-hard and provide an FPT algorithm when parameterized by $h$. Next, we conduct a study of the problem on common structural parameters like vertex cover number, maximum degree, treedepth, pathwidth and treewidth of one or both input graphs. We derive a complete dichotomy of parameterized results for our problem with respect to individual parameterizations as well as combinations of parameterizations from the above structural parameters. This provides us with a deep insight into the complexity theoretic and parameterized landscape of this problem.

Palash Dey, Sudeshna Kolay, Sipra Singh

We study the knapsack problem with graph theoretic constraints. That is, we assume that there exists a graph structure on the set of items of knapsack and the solution also needs to satisfy certain graph theoretic properties on top of knapsack constraints. In particular, we need to compute in the connected knapsack problem a connected subset of items which has maximum value subject to the size of knapsack constraint. We show that this problem is strongly NP-complete even for graphs of maximum degree four and NP-complete even for star graphs. On the other hand, we develop an algorithm running in time $O\left(2^{tw\log tw}\cdot\text{poly}(\min\{s^2,d^2\})\right)$ where $tw,s,d$ are respectively treewidth of the graph, size, and target value of the knapsack. We further exhibit a $(1-ε)$ factor approximation algorithm running in time $O\left(2^{tw\log tw}\cdot\text{poly}(n,1/ε)\right)$ for every $ε>0$. We show similar results for several other graph theoretic properties, namely path and shortest-path under the problem names path-knapsack and shortestpath-knapsack. Our results seems to indicate that connected-knapsack is computationally hardest followed by path-knapsack and shortestpath-knapsack.