Author name cluster

M.S. Ramanujan

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

JAIR Journal 2025 Journal Article

A Complexity-Theoretic Analysis of Majority Illusion in Social Networks

Umberto Grandi
Lawqueen Kanesh
Grzegorz Lisowski
M.S. Ramanujan
Paolo Turrini

Majority illusion occurs in a social network when the majority of the network vertices belong to a certain type but the majority of each vertex's neighbours belong to a different type, therefore creating the wrong perception, i.e., the illusion, that the majority type is different from the actual one. From a system engineering point of view, this motivates the search for algorithms to detect and, where possible, correct this often undesirable phenomenon. In this we provide a computational study of majority illusion in social networks, paying particular attention to the problem of its verification, i.e., whether majority illusion can occur on social networks, and elimination, i.e., how can we eliminate majority illusion by social network rewiring. While we show that the problems we consider are generally NP-complete, we also provide a parameterised complexity analysis, showing FPT-algorithms for the detection problem and W[1]-hardness for the elimination problem, using natural graph-theoretic parameters.

PDF Details DOI

TCS Journal 2020 Journal Article

Alternative parameterizations of Metric Dimension

Gregory Gutin
M.S. Ramanujan
Felix Reidl
Magnus Wahlström

A set of vertices W in a graph G is called resolving if for any two distinct x, y ∈ V ( G ), there is v ∈ W such that d G ( v, x ) ≠ d G ( v, y ), where d G ( u, v ) denotes the length of a shortest path between u and v in the graph G. The metric dimension md ( G ) of G is the minimum cardinality of a resolving set. The Metric Dimension problem, i. e. deciding whether md ( G ) ⩽ k, is NP-complete even for interval graphs (Foucaud et al. , 2017). We study Metric Dimension (for arbitrary graphs) from the lens of parameterized complexity. The problem parameterized by k was proved to be W [ 2 ] -hard by Hartung and Nichterlein (2013) and we study the dual parameterization, i. e. , the problem of whether md ( G ) ⩽ n − k, where n is the order of G. We prove that the dual parameterization admits (a) a kernel with at most 6 ( k + 1 ) vertices and (b) a randomized algorithm of runtime O ⁎ ( 4 k + o ( k ) ). Hartung and Nichterlein (2013) also observed that Metric Dimension is fixed-parameter tractable when parameterized by the vertex cover number v c ( G ) of the input graph. We complement this observation by showing that it does not admit a polynomial kernel even when parameterized by v c ( G ) + k, unless NP ⊆ coNP/poly. Our reduction also gives evidence for non-existence of polynomial Turing kernels. We also prove that Metric Dimension parameterized by bandwidth or cutwidth does not admit a polynomial kernel, unless NP ⊆ coNP/poly. Finally, using Eppstein's results (2015) we show that Metric Dimension parameterized by max-leaf number does admit a polynomial kernel.

Details DOI

TCS Journal 2020 Journal Article

Linear representation of transversal matroids and gammoids parameterized by rank

Pranabendu Misra
Fahad Panolan
M.S. Ramanujan
Saket Saurabh

Given a bipartite graph G = ( U ⊎ V, E ), a linear representation of the transversal matroid associated with G on the ground set U, can be constructed in randomized polynomial time. In fact one can get a linear representation deterministically in time 2 O ( m 2 n ), where m = | U | and n = | V |, by looping through all the choices made in the randomized algorithm. Other important matroids for which one can obtain linear representation deterministically in time similar to the one for transversal matroids include gammoids and strict gammoids. Strict gammoids are duals of transversal matroids and gammoids are restrictions of strict gammoids. We give faster deterministic algorithms to construct linear representations of transversal matroids, gammoids and strict gammoids. All our algorithms run in time ( m r ) m O ( 1 ), where m is the cardinality of the ground set and r is the rank of the matroid. In the language of parameterized complexity, we give an XP algorithm for finding linear representations of transversal matroids, gammoids and strict gammoids parameterized by the rank of the given matroid.

Details DOI

TCS Journal 2018 Journal Article

On the kernelization complexity of string problems

Manu Basavaraju
Fahad Panolan
Ashutosh Rai
M.S. Ramanujan
Saket Saurabh

In the Closest String problem we are given an alphabet Σ, a set of strings S = { s 1, s 2, …, s k } over Σ such that | s i | = n and an integer d. The objective is to check whether there exists a string s over Σ such that d H ( s, s i ) ≤ d, i ∈ { 1, …, k }, where d H ( x, y ) denotes the number of places strings x and y differ at. Closest String is a prototype string problem. This problem together with several of its variants such as Distinguishing String Selection and Closest Substring have been extensively studied from parameterized complexity perspective. These problems have been studied with respect to parameters that are combinations of k, d, | Σ | and n. However, surprisingly the kernelization question for these problems (for the versions when they admit fixed-parameter tractable algorithms) is not studied at all. In this paper we fill this gap in the literature and do a comprehensive study of these problems from kernelization complexity perspective. We settle almost all the problems by either obtaining a polynomial kernel or showing that the problem does not admit a polynomial kernel under a standard assumption in complexity theory.

Details DOI