Author name cluster

Lawqueen Kanesh

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.

15 papers

2 author rows

TCS Journal 2026 Journal Article

Exact and Parameterized Algorithms for Window Width Minimization in Bipartite Arrangement

Shashank Chauhan
Tanmay Inamdar
Lawqueen Kanesh
Sanjukta Roy

We study 2-layer Window Width Minimization in Bipartite arrangements, where given a bipartite arrangement G with bipartition A⊎B, and fixed and distinct integer positions for vertices in A, the goal is to determine distinct integer positions for vertices in B such that the window width parameter b is minimized. The window width b ensures that each vertex v ∈ B maintains a horizontal distance at most b from its neighbors in A and from its sibling vertices in B that share a common neighbor in A. In this paper, we design two exact exponential algorithms for Window Width Minimization: (1) an O * ( 4. 36 n · 2 p + n + b ) time and polynomial space algorithm and (2) O * ( 4. 899 n ) time and O * ( 2 n ) space algorithm, where | A | = p, | B | = n. We also initiate the study of the problem from the perspective of parameterized complexity and design a fixed-parameter tractable algorithm parameterized by the window size, which stands in stark contrast with the closely related Bandwidth Minimization problem. Specifically, our algorithm runs in O * ( b O ( b ) ) time and space, either finds an ordering of children with window width b, or correctly determines that no such ordering exists.

Details DOI

TCS Journal 2026 Journal Article

On approximability of propositional model counting

Diptarka Chakraborty
Lawqueen Kanesh
Kuldeep S. Meel

Propositional model counting problem ( # SAT) is a generalization of SAT, where the aim is to compute the number of satisfying assignments of a formula ϕ. Model counting is # P-complete even for 2-CNF, although checking the satisfiability of 2-CNF can be done in polynomial time. We consider # SAT parameterized by the treewidth (tw) of the primal graph of the input CNF formula. The best-known algorithm runs in time 2 t w n O ( 1 ), where n is the number of variables. One of the main challenges is whether we can have a faster algorithm, even if we allow a (multiplicative) approximation. This paper refutes such a possibility even for # 2-SAT assuming a popular complexity-theoretic assumption, namely the Strong Exponential Time Hypothesis (SETH). In particular, we show that for any ε, δ > 0, there cannot be a 2 ( 1 − ε ) t w n O ( 1 ) -time 2 n ( 1 − δ ) -approximation algorithm unless SETH is false. However, our lower bound does not hold for the monotone formulas. In fact, given a tree decomposition of width w for the primal graph of the input formula, for any ε > 0, we provide a 2 ( 1 − ε ) w n O ( 1 ) -time 2εn -approximation algorithm for the # Monotone-SAT.

Details DOI

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 2025 Journal Article

Burn and win

Pradeesha Ashok
Sayani Das
Lawqueen Kanesh
Saket Saurabh
Avi Tomar
Shaily Verma

Given a graph G and an integer k, the Graph Burning problem asks whether the graph G can be burned in at most k rounds. Graph burning is a model for information spreading in a network, where we study how fast the information spreads in the network through its vertices. In each round, the fire is started at an unburned vertex, and fire spreads from every burned vertex to all its neighbors in the subsequent round, burning all of them and so on. The minimum number of rounds required to burn the whole graph G is called the burning number of G. Graph Burning is known to be W[1]-hard when parameterized by the burning number and para-NP-hard when parameterized by treewidth. In this paper, we observe that Graph Burning is a special case of the Non-Uniform k-Center problem and prove the following results: – We give an explicit algorithm for the Non-Uniform k-Center problem parameterized by treewidth, maximum radius, and total number of centers. We extend this to show that Graph Burning is FPT parameterized by treewidth and burning number. This also gives an FPT algorithm for Graph Burning parameterized by burning number for apex-minor-free graphs. – Y. Kobayashi and Y. Otachi [Algorithmica 2022] proved that the problem is FPT parameterized by distance to cographs and gave a double exponential time FPT algorithm parameterized by distance to split graphs. We improve these results partially and give an FPT algorithm for the problem parameterized by distance to cographs ∩ split graphs (threshold graphs) that runs in 2 O ( t ln ⁡ t ) time. – We design a kernel of exponential size for Non-Uniform k-Center problem and Graph Burning in trees. – Furthermore, we give an exact algorithm to find the burning number of a graph that runs in time 2 n n O ( 1 ), where n is the number of vertices in the input graph.

Details DOI

I&C Journal 2025 Journal Article

Fixed-parameter algorithms for Fair Hitting Set problems

Tanmay Inamdar
Lawqueen Kanesh
Madhumita Kundu
Nidhi Purohit
Saket Saurabh

Selection of a group of representatives satisfying certain fairness constraints, is a commonly occurring scenario. Motivated by this, we initiate a systematic algorithmic study of a fair version of Hitting Set. In the classical Hitting Set problem, the input is a universe U, a family F of subsets of U, and a non-negative integer k. The goal is to determine whether there exists a subset S ⊆ U of size k that hits (i. e. , intersects) every set in F. Inspired by several recent works, we formulate a fair version of this problem, as follows. The input additionally contains a family B of subsets of U, where each subset in B can be thought of as the group of elements of the same type. We want to find a set S ⊆ U of size k that (i) hits all sets of F, and (ii) does not contain too many elements of each type. We call this problem Fair Hitting Set, and chart out its tractability boundary from both classical as well as multivariate perspective. Our results use a multitude of techniques from parameterized complexity including classical to advanced tools, such as, methods of representative sets for matroids, FO model checking, and a generalization of best known kernel for Hitting Set.

Details DOI

TCS Journal 2025 Journal Article

Max-SAT with cardinality constraint parameterized by the number of clauses

Pallavi Jain
Lawqueen Kanesh
Fahad Panolan
Souvik Saha
Abhishek Sahu
Saket Saurabh
Anannya Upasana

Max-SAT with cardinality constraint (CC-Max-SAT) is one of the classical NP-complete problems. In this problem, given a CNF-formula Φ on n variables, positive integers k and t, the goal is to find an assignment β with at most k variables set to true (also called a weight k -assignment) such that the number of clauses satisfied by β is at least t. The problem is known to be W [ 2 ] -hard with respect to the parameter k. In this paper, we study the problem with respect to the parameter t. The special case of CC-Max-SAT, when all the clauses contain only positive literals (known as Maximum Coverage), is known to admit a 2 O ( t ) n O ( 1 ) algorithm. We present a 2 O ( t ) n O ( 1 ) algorithm for the general case, CC-Max-SAT. We further study the problem through the lens of kernelization. Since Maximum Coverage does not admit polynomial kernel with respect to the parameter t, we focus our study on K d, d -free formulas (that is, the clause-variable incidence bipartite graph of the formula that excludes K d, d as a subgraph). Recently, in [Jain et al. , SODA 2023], an O ( d t d + 1 ) kernel has been designed for the Maximum Coverage problem on K d, d -free incidence graphs. We extend this result to CC-Max-SAT on K d, d -free formulas and design an O ( d 4 d 2 t d + 1 ) kernel.

Details DOI

MFCS Conference 2023 Conference Paper

Fixed-Parameter Algorithms for Fair Hitting Set Problems

Tanmay Inamdar 0002
Lawqueen Kanesh
Madhumita Kundu
Nidhi Purohit
Saket Saurabh 0001

Selection of a group of representatives satisfying certain fairness constraints, is a commonly occurring scenario. Motivated by this, we initiate a systematic algorithmic study of a fair version of Hitting Set. In the classical Hitting Set problem, the input is a universe 𝒰, a family ℱ of subsets of 𝒰, and a non-negative integer k. The goal is to determine whether there exists a subset S ⊆ 𝒰 of size k that hits (i. e. , intersects) every set in ℱ. Inspired by several recent works, we formulate a fair version of this problem, as follows. The input additionally contains a family ℬ of subsets of 𝒰, where each subset in ℬ can be thought of as the group of elements of the same type. We want to find a set S ⊆ 𝒰 of size k that (i) hits all sets of ℱ, and (ii) does not contain too many elements of each type. We call this problem Fair Hitting Set, and chart out its tractability boundary from both classical as well as multivariate perspective. Our results use a multitude of techniques from parameterized complexity including classical to advanced tools, such as, methods of representative sets for matroids, FO model checking, and a generalization of best known kernels for Hitting Set.

Details

AAAI Conference 2023 Conference Paper

Identifying and Eliminating Majority Illusion in Social Networks

Umberto Grandi
Lawqueen Kanesh
Grzegorz Lisowski
Ramanujan Sridharan
Paolo Turrini

PDF Details DOI

SODA Conference 2023 Conference Paper

Parameterized Approximation Scheme for Biclique-free Max k -Weight SAT and Max Coverage

Pallavi Jain 0001
Lawqueen Kanesh
Fahad Panolan
Souvik Saha 0002
Abhishek Sahu
Saket Saurabh 0001
Anannya Upasana

MAX-SAT with cardinality constraint (CC-MAX-SAT) is one of the classical NP-complete problems, that generalizes MAXIMUM COVERAGE, PARTIAL VERTEX COYER, MAX-2-SAT with bisection constraints, and has been extensively studied across all algorithmic paradigms. In this problem, we are given a CNF-formula Φ, and a positive integer k, and the goal is to find an assignment β with at most k variables set to true (also called a weight k -assignment) such that the number of clauses satisfied by β is maximized. The problem is known to admit an approximation algorithm with factor, which is probably optimal. In fact, the problem is hard to approximate within 0. 944, assuming Unique Games Conjecture, even when the input formula is 2-CNF. Furthermore, assuming Gap-Exponential Time Hypothesis (Gap-ETH), for any ε > 0 and any function h, no h(k)(n + m ) o ( k ) time algorithm can approximate MAXIMUM COVERAGE (a monotone version of CC-MAX-SAT) with n elements and m sets to within a factor, even with a promise that there exist k sets that fully cover the whole universe. These intractable results lead us to explore families of formula, where we can circumvent these barriers. Towards this we consider K d, d -free formulas (that is, the clause-variable incidence bipartite graph of the formula excludes K d, d as an induced subgraph). We show that for every ε > 0, there exists an algorithm for CC-MAX-SAT on K d, d -free formulas with approximation ratio (1 — ε) and running in time (these algorithms are called FPT-AS). For, MAXIMUM COVERAGE on K d, d -free set families, we obtain FPT-AS with running time. Our second result considers “optimizing k ”, with fixed covering constraint for the Maximum Coverage problem. To explain our result, we first recast the MAXIMUM COVERAGE problem as the MAX RED BLUE DOMINATING SET WITH COVERING CONSTRAINT problem. Here, input is a bipartite graph G = (A, B, E), a positive integer t, and the objective is to find a minimum sized subset S ⊆ A, such that | N ( S )| (the size of the set of neighbors of S ) is at least t. We design an additive approximation algorithm for MAX RED BLUE DOMINATING SET WITH COVERING CONSTRAINT, on K d, d -free bipartite graphs, running in FPT time. In particular, if k denotes the minimum size of S ⊆ A, such that | N ( S )| ≥ t, then our algorithm runs in time ( kd ) O ( kd ) n O (1) and returns a set S ' such that | N ( S' )| ≥ t and | S' | ≤ k +1. This is in sharp contrast to the fact that, even a special case of our problem, namely, the PARTIAL VERTEX COVER problem (or MAX k -VC) is W[1]-hard, parameterized by k. Thus, we get the best possible parameterized approximation algorithm for the MAXIMUM COVERAGE problem on K d, d -free bipartite graphs. * Pallavi Jain is supported by Seed Grant (IITJ/R&D/2022-23/07) and SERB-SUPRA Grant(SPR/2021/000860). Lawqueen Kanesh is supported by EPSRC Standard Research Grant (EP/V044621/1). Saket Saurabh is supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No. 819416); and he also acknowledges the support of Swarnajayanti Fellowship grant DST/SJF/MSA-01/2017-18.

Details

SODA Conference 2022 Conference Paper

Deleting, Eliminating and Decomposing to Hereditary Classes Are All FPT-Equivalent

Akanksha Agrawal 0001
Lawqueen Kanesh
Daniel Lokshtanov
Fahad Panolan
M. S. Ramanujan 0001
Saket Saurabh 0001
Meirav Zehavi

Vertex-deletion problems have been at the heart of parameterized complexity throughout its history. Here, the aim is to determine the minimum size (denoted by mod ℋ ) of a modulator to a graph class ℋ, i. e. , a set of vertices whose deletion results in a graph in ℋ. Recent years have seen the development of a research programme where the complexity of modulators is measured in ways other than size. For instance, for a graph class ℋ, the graph parameters elimination distance to ℋ (denoted by ed ℋ ) [Bulian and Dawar, Algorithmica, 2016] and ℋ -treewidth (denoted by tw ℋ ) [Eiben et al. JCSS, 2021] aim to minimize the treedepth and treewidth, respectively, of the “torso” of the graph induced on a modulator to the graph class ℋ. Here, the torso of a vertex set S in a graph G is the graph with vertex set S and an edge between two vertices u, v ∊ S if there is a path between u and v in G whose internal vertices all lie outside S. In this paper, we show that from the perspective of (non-uniform) fixed-parameter tractability (FPT), the three parameters described above give equally powerful parameterizations for every hereditary graph class ℋ that satisfies mild additional conditions. In fact, we show that for every hereditary graph class ℋ satisfying mild additional conditions, with the exception of ed ℋ parameterized by tw ℋ, for every pair of these parameters, computing one parameterized by itself or any of the others is FPT-equivalent to the standard vertex-deletion (to ℋ ) problem. As an example, we prove that an FPT algorithm for the vertex-deletion problem implies a non-uniform FPT algorithm for computing ed ℋ and tw ℋ. The conclusions of non-uniform FPT algorithms being somewhat unsatisfactory, we essentially prove that if ℋ is hereditary, union-closed, CMSO-definable, and (a) the canonical equivalence relation (or any refinement thereof) for membership in the class can be efficiently computed, or (b) the class admits a “strong irrelevant vertex rule”, then there exists a uniform FPT algorithm for ed ℋ. Using these sufficient conditions, we obtain uniform FPT algorithms for computing ed ℋ, when ℋ is defined by excluding a finite number of connected (a) minors, or (b) topological minors, or (c) induced subgraphs, or when ℋ is any of bipartite, chordal or interval graphs. For most of these problems, the existence of a uniform FPT algorithm has remained open in the literature. In fact, for some of them, even a non-uniform FPT algorithm was not known. For example, Jansen et al. [STOC 2021] ask for such an algorithm when ℋ is defined by excluding a finite number of connected topological minors. We resolve their question in the affirmative.

Details

TCS Journal 2022 Journal Article

On the complexity of singly connected vertex deletion

Avinandan Das
Lawqueen Kanesh
Jayakrishnan Madathil
Komal Muluk
Nidhi Purohit
Saket Saurabh

A digraph D is singly connected if for all ordered pairs of vertices u, v ∈ V ( D ), there is at most one path in D from u to v. In this paper, we study the Singly Connected Vertex Deletion (SCVD) problem: Given an n-vertex digraph D and a positive integer k, does there exist a set S ⊆ V ( D ) such that | S | ≤ k and D − S is singly connected? This problem may be seen as a directed counterpart of the (Undirected) Feedback Vertex Set problem, as an undirected graph is singly connected if and only if it is acyclic. SCVD is known to be NP-hard on general digraphs. We study the complexity of SCVD on various classes of digraphs such as tournaments, and various generalisations of tournaments such as digraphs of bounded independence number, in- and out-tournaments and local tournaments. We show that unlike the Feedback Vertex Set on Tournaments (FVST) problem, SCVD is polynomial-time solvable on tournaments. In addition, we show that SCVD is polynomial-time solvable on digraphs of bounded independence number, and on the class of acyclic local tournaments. We also study the parameterized complexity of SCVD, with k as the parameter, on the class of in-tournaments. And we show that on in-tournaments, SCVD admits a fixed-parameter tractable algorithm and a quadratic vertex kernel. We also show that on the class of local tournaments, which is a sub-class of in-tournaments, SCVD admits a linear vertex kernel.

Details DOI

TCS Journal 2021 Journal Article

Parameterized complexity of fair feedback vertex set problem

Lawqueen Kanesh
Soumen Maity
Komal Muluk
Saket Saurabh

Given a graph G = ( V, E ), a subset S ⊆ V ( G ) is said to be a feedback vertex set of G if G − S is a forest. In the Feedback Vertex Set (FVS) problem, we are given an undirected graph G, and a positive integer k, the question is whether there exists a feedback vertex set of size at most k. In this paper, we study three variants of the FVS problem: Unrestricted Fair FVS, Restricted Fair FVS, and Relaxed Fair FVS. In Unrestricted Fair FVS, we are given a graph G and a positive integer ℓ, the question is does there exist a feedback vertex set S ⊆ V ( G ) (of any size) such that for every vertex v ∈ V ( G ), v has at most ℓ neighbours in S. First, we study Unrestricted Fair FVS from different parameterizations such as treewidth, treedepth, and neighbourhood diversity and obtain several results (both tractability and intractability). Next, we study Restricted Fair FVS, where we are also given an integer k in the input and we demand the size of S to be at most k. This problem is trivially NP-complete; we show that Restricted Fair FVS when parameterized by the solution size k and the maximum degree Δ of the graph G, admits a kernel of size O ( Δ k ). Finally, we study the Relaxed Fair FVS problem, where we want that the size of S is at most k and for every vertex v outside S, v has at most ℓ neighbours in S. We give an FPT algorithm for Relaxed Fair FVS problem running in time c k n O ( 1 ), for a fixed constant c.

Details DOI

TCS Journal 2021 Journal Article

Paths to trees and cacti

Akanksha Agrawal
Lawqueen Kanesh
Saket Saurabh
Prafullkumar Tale

We know that Tree Contraction does not admit a polynomial kernel unless NP ⊆ coNP/poly, while Path Contraction admits a kernel with O ( k ) vertices. The starting point of this article is the following natural questions: What is the structure of the family of paths that allows Path Contraction to admit a polynomial kernel? Apart from the size of the solution, what other additional parameters should we consider so we can design polynomial kernels for these basic contraction problems? To design polynomial kernels, we consider the family of trees with the bounded number of leaves (note that the family of paths are trees with at most two leaves). In particular, we study Bounded Tree Contraction. Here, an input is a graph G, integers k and ℓ, and the goal is to decide whether, there is a subset F ⊆ E ( G ) of size at most k such that G / F is a tree with at most ℓ leaves. We design a kernel with O ( k ℓ ) vertices and O ( k 2 + k ℓ ) edges for this problem. We complement this result by giving kernelization lower bound. We also prove similar results for Bounded Out-Tree Contraction and Bounded Cactus Contraction.

Details DOI

MFCS Conference 2019 Conference Paper

Parameterized Complexity of Conflict-Free Matchings and Paths

Akanksha Agrawal 0001
Pallavi Jain 0001
Lawqueen Kanesh
Saket Saurabh 0001

An input to a conflict-free variant of a classical problem Gamma, called Conflict-Free Gamma, consists of an instance I of Gamma coupled with a graph H, called the conflict graph. A solution to Conflict-Free Gamma in (I, H) is a solution to I in Gamma, which is also an independent set in H. In this paper, we study conflict-free variants of Maximum Matching and Shortest Path, which we call Conflict-Free Matching (CF-Matching) and Conflict-Free Shortest Path (CF-SP), respectively. We show that both CF-Matching and CF-SP are W[1]-hard, when parameterized by the solution size. Moreover, W[1]-hardness for CF-Matching holds even when the input graph where we want to find a matching is itself a matching, and W[1]-hardness for CF-SP holds for conflict graph being a unit-interval graph. Next, we study these problems with restriction on the conflict graphs. We give FPT algorithms for CF-Matching when the conflict graph is chordal. Also, we give FPT algorithms for both CF-Matching and CF-SP, when the conflict graph is d-degenerate. Finally, we design FPT algorithms for variants of CF-Matching and CF-SP, where the conflicting conditions are given by a (representable) matroid.

Details

MFCS Conference 2018 Conference Paper

Conflict Free Feedback Vertex Set: A Parameterized Dichotomy

Akanksha Agrawal 0001
Pallavi Jain 0001
Lawqueen Kanesh
Daniel Lokshtanov
Saket Saurabh 0001

In this paper we study recently introduced conflict version of the classical Feedback Vertex Set (FVS) problem. For a family of graphs F, we consider the problem F-CF-Feedback Vertex Set (F-CF-FVS, for short). The F-CF-FVS problem takes as an input a graph G, a graph H in F (where V(G)=V(H)), and an integer k, and the objective is to decide if there is a set S subseteq V(G) of size at most k such that G-S is a forest and S is an independent set in H. Observe that if we instantiate F to be the family of edgeless graphs then we get the classical FVS problem. Jain, Kanesh, and Misra [CSR 2018] showed that in contrast to FVS, F-CF-FVS is W[1]-hard on general graphs and admits an FPT algorithm if F is the family of d-degenerate graphs. In this paper, we relate F-CF-FVS to the Independent Set problem on special classes of graphs, and obtain a complete dichotomy result on the Parameterized Complexity of the problem F-CF-FVS, when F is a hereditary graph family. In particular, we show that F-CF-FVS is FPT parameterized by the solution size if and only if F+Cluster IS is FPT parameterized by the solution size. Here, F+Cluster IS is the Independent Set problem in the (edge) union of a graph G in F and a cluster graph H (G and H are explicitly given). Next, we exploit this characterization to obtain new FPT results as well as intractability results for F-CF-FVS. In particular, we give an FPT algorithm for F+Cluster IS when F is the family of K_{i, j}-free graphs. We show that for the family of bipartite graph B, B-CF-FVS is W[1]-hard, when parameterized by the solution size. Finally, we consider, for each 0< epsilon<1, the family of graphs F_epsilon, which comprise of graphs G such that |E(G)| <= |V(G)|^(2-epsilon), and show that F_epsilon-CF-FVS is W[1]-hard, when parameterized by the solution size, for every 0<epsilon<1.

Details