Vijayaragunathan Ramamoorthi

Mr. Vijayaragunathan Ramamoorthi

Indian Institute of Technology Madras
orcid

Research Focus & Metrics

Academic Career Length

9Years (2018-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
28 September 2023
Verified
Book Chapter
Open access
PDF file
MFMichael R. Fellows
Michael R. Fellows
MGMario Grobler
Mario Grobler
NMNicole Megow
Nicole Megow
AMAmer E. Mouawad
Amer E. Mouawad
VRVijayaragunathan Ramamoorthi
Vijayaragunathan Ramamoorthi
SSSebastian Siebertz
Sebastian Siebertz
The dynamics of real-world applications and systems require efficient methods for improving infeasible solutions or restoring corrupted ones by making modifications to the current state of a system in a restricted way. We propose a new framework of solution discovery via reconfiguration for constructing a feasible solution for a given problem by executing a sequence of small modifications starting from a given state. Our framework integrates different aspects of classical local search, reoptimization, and combinatorial reconfiguration. We exemplify our framework on a multitude of fundamental combinatorial problems, namely VERTEX COVER, INDEPENDENT SET, DOMINATING SET, and COLORING. We study the classical as well as the parameterized complexity of the solution discovery variants of those problems and explore the boundary between tractable and intractable instances.

25 April 2018
Verified
Book Chapter
Closed access
PDF file
NNN. S. Narayanaswamy
N. S. Narayanaswamy
MNMeghana Nasre
Meghana Nasre
VRVijayaragunathan Ramamoorthi
Vijayaragunathan Ramamoorthi

19 December 2019 in Algorithms
Verified
Journal Article
Open access
PDF file
NNN. S. Narayanaswamy
N. S. Narayanaswamy
VRVijayaragunathan Ramamoorthi
Vijayaragunathan Ramamoorthi
We present a detailed survey of results and two new results on graphical models of uncertainty and associated optimization problems. We focus on two well-studied models, namely, the Random Failure (RF) model and the Linear Reliability Ordering (LRO) model. We present an FPT algorithm parameterized by the product of treewidth and max-degree for maximizing expected coverage in an uncertain graph under the RF model. We then consider the problem of finding the maximal core in a graph, which is known to be polynomial time solvable. We show that the Probabilistic-Core problem is polynomial time solvable in uncertain graphs under the LRO model. On the other hand, under the RF model, we show that the Probabilistic-Core problem is W[1]-hard for the parameter d, where d is the minimum degree of the core. We then design an FPT algorithm for the parameter treewidth.

13 June 2023 in Algorithmica
Verified
Journal Article
Closed access
PDF file
AAAkanksha Agrawal
Akanksha Agrawal
PCPratibha Choudhary
Pratibha Choudhary
NNN. S. Narayanaswamy
N. S. Narayanaswamy
KNK. K. Nisha
K. K. Nisha
VRVijayaragunathan Ramamoorthi
Vijayaragunathan Ramamoorthi

Verified
Conference Paper
Open access
KCKeerti Choudhary
Keerti Choudhary
ACAvi Cohen
Avi Cohen
NNN. S. Narayanaswamy
N. S. Narayanaswamy
DPDavid Peleg
David Peleg
VRVijayaragunathan Ramamoorthi
Vijayaragunathan Ramamoorthi
We study the Budgeted Dominating Set (BDS) problem on uncertain graphs, namely, graphs with a probability distribution p associated with the edges, such that an edge e exists in the graph with probability p(e). The input to the problem consists of a vertex-weighted uncertain graph 𝒢 = (V, E, p, ω) and an integer budget (or solution size) k, and the objective is to compute a vertex set S of size k that maximizes the expected total domination (or total weight) of vertices in the closed neighborhood of S. We refer to the problem as the Probabilistic Budgeted Dominating Set (PBDS) problem. In this article, we present the following results on the complexity of the PBDS problem. 1) We show that the PBDS problem is NP-complete even when restricted to uncertain trees of diameter at most four. This is in sharp contrast with the well-known fact that the BDS problem is solvable in polynomial time in trees. We further show that PBDS is 𝖶[1]-hard for the budget parameter k, and under the Exponential time hypothesis it cannot be solved in n^o(k) time. 2) We show that if one is willing to settle for (1-ε) approximation, then there exists a PTAS for PBDS on trees. Moreover, for the scenario of uniform edge-probabilities, the problem can be solved optimally in polynomial time. 3) We consider the parameterized complexity of the PBDS problem, and show that Uni-PBDS (where all edge probabilities are identical) is 𝖶[1]-hard for the parameter pathwidth. On the other hand, we show that it is FPT in the combined parameters of the budget k and the treewidth. 4) Finally, we extend some of our parameterized results to planar and apex-minor-free graphs. Our first hardness proof (Thm. 1) makes use of the new problem of k-Subset Σ-Π Maximization (k-SPM), which we believe is of independent interest. We prove its NP-hardness by a reduction from the well-known k-SUM problem, presenting a close relationship between the two problems.

10 March 2022 in Theory of Computing Systems
Verified
Journal Article
Open access
PDF file
FFFedor V. Fomin
Fedor V. Fomin
VRVijayaragunathan Ramamoorthi
Vijayaragunathan Ramamoorthi
The Maximum Covering Location Problem (MCLP) is a well-studied problem in the field of operations research. Given a network with positive or negative demands on the nodes, a positive integer k, the MCLP seeks to find k potential facility centers in the network such that the neighborhood coverage is maximized. We study the variant of MCLP where edges of the network are subject to random failures due to some disruptive events. One of the popular models capturing the unreliable nature of the facility location is the linear reliability ordering (LRO) model. In this model, with every edge e of the network, we associate its survival probability 0 ≤ pe ≤ 1, or equivalently, its failure probability 1 − pe. The failure correlation in LRO is the following: If an edge e fails then every edge $e^{\prime }$ e ′ with $p_{e^{\prime }} \leq p_{e}$ p e ′ ≤ p e surely fails. The task is to identify the positions of k facilities that maximize the expected coverage. We refer to this problem as Expected Coverage problem. We study the Expected Coverage problem from the parameterized complexity perspective and obtain the following results. 1. For the parameter pathwidth, we show that the Expected Coverage problem is W[1]-hard. We find this result a bit surprising, because the variant of the problem with non-negative demands is fixed-parameter tractable (FPT) parameterized by the treewidth of the input graph. 2. We complement the lower bound by the proof that Expected Coverage is FPT being parameterized by the treewidth and the maximum vertex degree. We give an algorithm that solves the problem in time $ 2^{{\mathcal {O}}({\textbf {tw}} \log {\varDelta })} n^{{\mathcal {O}}(1)}$ 2 O ( tw log Δ ) n O ( 1 ) , where tw is the treewidth, Δ is the maximum vertex degree, and n the number of vertices of the input graph. In particular, since Δ ≤ n, it means the problem is solvable in time $ n^{{\mathcal {O}}({\textbf {tw}})} $ n O ( tw ) , that is, is in XP parameterized by treewidth.