Author name cluster

Ashutosh Rai

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.

5 papers

1 author row

TCS Journal 2026 Journal Article

On the parameterized complexity of diverse SAT

Neeldhara Misra
Harshil Mittal
Ashutosh Rai

We study the Boolean Satisfiability problem (SAT) in the framework of diversity, where one asks for multiple solutions that are mutually far apart (i. e. , sufficiently dissimilar from each other) for a suitable notion of distance/dissimilarity between solutions. Interpreting assignments as bit vectors, we take their Hamming distance to quantify dissimilarity, and we focus on the problem of finding two solutions. Specifically, we define the problem Max Differ SAT (resp. Exact Differ SAT) as follows: Given a Boolean formula ϕ on n variables, decide whether ϕ has two satisfying assignments that differ on at least (resp. exactly) d variables. We study the classical and parameterized (in parameters d and n − d ) complexities of Max Differ SAT and Exact Differ SAT, when restricted to some classes of formulas on which SAT is known to be polynomial-time solvable. In particular, we consider affine formulas, Krom formulas (i. e. , 2-CNF formulas) and hitting formulas. For affine formulas, we show the following: Both problems are polynomial-time solvable when each equation has at most two variables. Exact Differ SAT is NP -hard, even when each equation has at most three variables and each variable appears in at most four equations. Also, Max Differ SAT is NP -hard, even when each equation has at most four variables. Both problems are W [ 1 ] -hard in the parameter n − d. In contrast, when parameterized by d, Exact Differ SAT is W [ 1 ] -hard, but Max Differ SAT admits a single-exponential FPT algorithm and a polynomial-kernel. For Krom formulas, we show the following: Both problems are polynomial-time solvable when each variable appears in at most two clauses. Also, both problems are W [ 1 ] -hard in the parameter d (and therefore, it turns out, also NP -hard), even on monotone inputs (i. e. , formulas with no negative literals). Finally, for hitting formulas, we show that both problems can be solved in polynomial-time.

Details DOI

TCS Journal 2024 Journal Article

Parameterized approximation algorithms for weighted vertex cover

Soumen Mandal
Pranabendu Misra
Ashutosh Rai
Saket Saurabh

A vertex cover of a graph is a set of vertices of the graph such that every edge has at least one endpoint in it. In this work, we study Weighted Vertex Cover with solution size as a parameter. Formally, in the ( k, W ) -Vertex Cover problem, given a graph G, an integer k, a positive rational W, and a weight function w: V ( G ) → Q +, the question is whether G has a vertex cover of size at most k of weight at most W, with k being the parameter. An ( a, b ) -bi-criteria approximation algorithm for ( k, W ) -Vertex Cover either produces a vertex cover S such that | S | ≤ a k and w ( S ) ≤ b W, or decides that there is no vertex cover of size at most k of weight at most W. We obtain the following results. • A simple ( 2, 2 ) -bi-criteria approximation algorithm for ( k, W ) -Vertex Cover in polynomial time by modifying the standard LP-rounding algorithm. • A simple exact parameterized algorithm for ( k, W ) -Vertex Cover running in O ⁎ ( 1. 4656 k ) time 1. • A ( 1 + ϵ, 2 ) -approximation algorithm for ( k, W ) -Vertex Cover running in O ⁎ ( 1. 4656 ( 1 − ϵ ) k ) time. • A ( 1. 5, 1. 5 ) -approximation algorithm for ( k, W ) -Vertex Cover running in O ⁎ ( 1. 414 k ) time. • A ( 2 − δ, 2 − δ ) -approximation algorithm for ( k, W ) -Vertex Cover running in O ⁎ ( ∑ i = δ k ( 1 − 2 δ ) 1 + 2 δ δ k ( 1 − 2 δ ) 2 δ ( δ k + i δ k − 2 i δ 1 − 2 δ ) ) time for any δ < 0. 5. For example, for ( 1. 75, 1. 75 ) and ( 1. 9, 1. 9 ) -approximation algorithms, we get running times of O ⁎ ( 1. 272 k ) and O ⁎ ( 1. 151 k ) respectively. Our algorithms (expectedly) do not improve upon the running times of the existing algorithms for the unweighted version of Vertex Cover. When compared to algorithms for the weighted version, our algorithms are the first ones to the best of our knowledge which work with arbitrary weights, and they perform well when the solution size is much smaller than the total weight of the desired solution.

Details DOI

TCS Journal 2021 Journal Article

Belief-invariant and quantum equilibria in games of incomplete information

Vincenzo Auletta
Diodato Ferraioli
Ashutosh Rai
Giannicola Scarpa
Andreas Winter

Drawing on ideas from game theory and quantum physics, we investigate nonlocal correlations from the point of view of equilibria in games of incomplete information. These equilibria can be classified in decreasing power as general communication equilibria, belief-invariant equilibria and correlated equilibria, all of which contain the familiar Nash equilibria. The notion of belief-invariant equilibrium appeared in game theory in the 90s. However, the class of non-signalling correlations associated to belief-invariance arose naturally already in the 80s in the foundations of quantum mechanics. In the present work, we explain and unify these two origins of the idea and study the above classes of equilibria, together with quantum correlated equilibria, using tools from quantum information but the language of (algorithmic) game theory. We present a general framework of belief-invariant communication equilibria, which contains correlated equilibria and quantum correlated equilibria as special cases. Our framework also contains the theory of Bell inequalities and their violations due to non-locality, which is a question of intense interest in the foundations of quantum mechanics, and it was indeed the original motivation for the aforementioned studies. Moreover, in our framework we can also model quantum games where players have conflicting interests, a recent developing topic in physics. We then use our framework to show new results related to the social welfare of equilibria. Namely, we exhibit a game where belief-invariance is socially better than any correlated equilibrium, and a game where all non-belief-invariant communication equilibria have a suboptimal social welfare. We also show that optimal social welfare can in certain cases be achieved by quantum mechanical correlations, which do not need an informed mediator to be implemented, and go beyond the classical “sunspot” or shared randomness approach.

Details DOI

TCS Journal 2018 Journal Article

Bivariate complexity analysis of Almost Forest Deletion

Ashutosh Rai
Saket Saurabh

In this paper we study a generalization of classic Feedback Vertex Set problem in the realm of multivariate complexity analysis. We say that a graph F is an l-forest if we can delete at most l edges from F to get a forest. That is, F is at most l edges away from being a forest. In this paper we introduce the Almost Forest Deletion problem, where given a graph G and integers k and l, the question is whether there exists a subset of at most k vertices such that its deletion leaves us an l-forest. We show that this problem admits an algorithm with running time 2 O ( k + l ) n O ( 1 ) and a kernel of size O ( k l ( k + l ) ). We also show that the problem admits a 2 O ( tw ) n O ( 1 ) algorithm on bounded treewidth graphs, using which we design a subexponential algorithm for the problem on planar graphs.

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