- Kanesh, Lawqueen

###### Options

# Kanesh, Lawqueen

Loading...

Preferred name

Kanesh, Lawqueen

Alternative Name

Kanesh, L.

Kanesh L.

Main Affiliation

Email

Scopus Author ID

Researcher ID

13 results Back to results

### Filters

##### Date

##### Author

##### Subject

##### Has files

##### Type

### Settings

Sort By

Results per page

Now showing 1 - 10 of 13

- PublicationDecremental Sensitivity Oracles for Covering and Packing Minors(2024-03-01)
; ;Panolan, Fahad ;Ramanujan, M. S.Strulo, PeterShow more In this paper, we present the first decremental fixed-parameter sensitivity oracles for a number of basic covering and packing problems on graphs. In particular, we obtain the first decremental sensitivity oracles for Vertex Planarization (delete k vertices to make the graph planar) and Cycle Packing (pack k vertex-disjoint cycles in the given graph). That is, we give a sensitivity oracle that preprocesses the given graph in time f(k, ℓ)nO(1) such that, when given a set of ℓ edge deletions, the data structure decides in time f(k, ℓ) whether the updated graph is a positive instance of the problem. These results are obtained as a corollary of our central result, which is the first decremental sensitivity oracle for Topological Minor Deletion (cover all topological minors in the input graph that belong to a specified set, using k vertices). Though our methodology closely follows the literature, we are able to produce the first explicit bounds on the preprocessing and query times for several problems. We also initiate the study of fixed-parameter sensitivity oracles with so-called structural parameterizations and give sufficient conditions for the existence of fixed-parameter sensitivity oracles where the parameter is just the treewidth of the graph. In contrast, all existing literature on this topic and the aforementioned results in this paper assume a bound on the solution size (a weaker parameter than treewidth for many problems). As corollaries, we obtain decremental sensitivity oracles for well-studied problems such as Vertex Cover and Dominating Set when only the treewidth of the input graph is bounded. A feature of our methodology behind these results is that we are able to obtain query times independent of treewidth.Show more - PublicationIdentifying and Eliminating Majority Illusion in Social Networks(2023-06-27)
;Grandi, Umberto; ;Lisowski, Grzegorz ;Sridharan, RamanujanTurrini, PaoloShow more 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 undesirable phenomenon. In this paper we initiate the computational study of majority illusion in social networks, providing NP-hardness and parametrised complexity results for its occurrence and elimination.Show more - PublicationParameterized Approximation Scheme for Biclique-free Max k-Weight SAT and Max Coverage(2023-01-01)
; ; ;Panolan, Fahad ;Saha, Souvik ;Sahu, Abhishek ;Saurabh, SaketUpasana, AnannyaShow more Max-SAT with cardinality constraint (CC-Max-Sat) is one of the classical NP-complete problems, that generalizes Maximum Coverage, Partial Vertex Cover, 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 (Equation presented) 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 (Equation presented) time algorithm can approximate Maximum Coverage (a monotone version of CC-Max-Sat) with n elements and m sets to within a factor (Equation presented), 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 Kd, d-free formulas (that is, the clause-variable incidence bipartite graph of the formula excludes Kd, d as an induced subgraph). We show that for every ϵ > 0, there exists an algorithm for CC-Max-Sat on Kd, d-free formulas with approximation ratio (1−ϵ) and running in time (Equation presented) (these algorithms are called FPT-AS). For, Maximum Coverage on Kd, d-free set families, we obtain FPT-AS with running time (Equation presented). 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 Kd, 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 (Equation presented) 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 Kd, d-free bipartite graphs.Show more - PublicationParameterized complexity of feedback vertex sets on hypergraphs(2020-12-01)
;Choudhary, Pratibha; ;Lokshtanov, Daniel ;Panolan, FahadSaurabh, SaketShow more A feedback vertex set in a hypergraph H is a set of vertices S such that deleting S from H results in an acyclic hypergraph. Here, deleting a vertex means removing the vertex and all incident hyperedges, and a hypergraph is acyclic if its vertex-edge incidence graph is acyclic. We study the (parameterized complexity of) the Hypergraph Feedback Vertex Set (HFVS) problem: given as input a hypergraph H and an integer k, determine whether H has a feedback vertex set of size at most k. It is easy to see that this problem generalizes the classic Feedback Vertex Set (FVS) problem on graphs. Remarkably, despite the central role of FVS in parameterized algorithms and complexity, the parameterized complexity of a generalization of FVS to hypergraphs has not been studied previously. In this paper, we fill this void. Our main results are as follows HFVS is W[2]-hard (as opposed to FVS, which is fixed parameter tractable). If the input hypergraph is restricted to a linear hypergraph (no two hyperedges intersect in more than one vertex), HFVS admits a randomized algorithm with running time 2O(k3 log k)nO(1). If the input hypergraph is restricted to a d-hypergraph (hyperedges have cardinality at most d), then HFVS admits a deterministic algorithm with running time dO(k)nO(1). The algorithm for linear hypergraphs combines ideas from the randomized algorithm for FVS by Becker et al. [J. Artif. Intell. Res., 2000] with the branching algorithm for Point Line Cover by Langerman and Morin [Discrete & Computational Geometry, 2005].Show more Scopus© Citations 1 - PublicationFPT Approximations for Packing and Covering Problems Parameterized by Elimination Distance and Even Less(2023-12-01)
; ; ;Kundu, Madhumita ;Ramanujan, M. S.Saurabh, SaketShow more For numerous graph problems in the realm of parameterized algorithms, using the size of a smallest deletion set (called a modulator) into well-understood graph families as parameterization has led to a long and successful line of research. Recently, however, there has been an extensive study of structural parameters that are potentially much smaller than the modulator size. In particular, recent papers [Jansen et al. STOC 2021; Agrawal et al. SODA 2022] have studied parameterization by the size of the modulator to a graph family H (modH()), elimination distance to H (edH()), and H-treewidth (twH()). These parameters are related by the fact that twH lower bounds edH, which in turn lower bounds modH. While these new parameters have been successfully exploited to design fast exact algorithms their utility (especially that of edH and twH) in the context of approximation algorithms is mostly unexplored. The conceptual contribution of this paper is to present novel algorithmic meta-theorems that expand the impact of these structural parameters to the area of FPT Approximation, mirroring their utility in the design of exact FPT algorithms. Precisely, we show that if a covering or packing problem is definable in Monadic Second Order Logic and has a property called Finite Integer Index (FII), then the existence of an FPT Approximation Scheme (FPT-AS, i.e., (1)-approximation) parameterized by modH(), edH(), and twH() is in fact equivalent. As a consequence, we obtain FPT-ASes for a wide range of covering, packing, and domination problems on graphs with respect to these parameters. In the process, we show that several graph problems, that are W[1]-hard parameterized by modH, admit FPT-ASes not only when parameterized by modH, but even when parameterized by the potentially much smaller parameter twH(). In the spirit of [Agrawal et al. SODA 2022], our algorithmic results highlight a broader connection between these parameters in the world of approximation. As concrete exemplifications of our meta-theorems, we obtain FPT-ASes for well-studied graph problems such as Vertex Cover, Feedback Vertex Set, Cycle Packing and Dominating Set, parameterized by twH() (and hence, also by modH() or edH()), where H is any family of minor free graphs.Show more - PublicationMax-SAT with Cardinality Constraint Parameterized by the Number of Clauses(2024-01-01)
; ; ;Panolan, Fahad ;Saha, Souvik ;Sahu, Abhishek ;Saurabh, SaketUpasana, AnannyaShow more 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, 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 2O(t)nO(1) algorithm. We present a 2O(t)nO(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 Kd,d-free formulas (that is, the clause-variable incidence bipartite graph of the formula that excludes Kd,d as a subgraph). Recently, in [Jain et al., SODA 2023], an O(dtd+1) kernel has been designed for the Maximum Coverage problem on Kd,d-free incidence graphs. We extend this result to Max-SAT on Kd,d-free formulas and design a O(d4d2td+1) kernel.Show more - PublicationFixed-Parameter Algorithms for Fair Hitting Set Problems(2023-08-01)
; ;Kundu, Madhumita ;Purohit, Nidhi ;Saurabh, SaketShow more 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 kernels for Hitting Set.Show more - PublicationOn the Parameterized Complexity of Minus Domination(2024-01-01)
;Bhyravarapu, Sriram; ;Mohanapriya, A. ;Purohit, Nidhi ;Sadagopan, N.Saurabh, SaketShow more Dominating Set is a well-studied combinatorial problem. Given a graph G=(V,E), a dominating function f:V(G)→{0,1} is a labeling of the vertices of G such that ∑w∈N[v]f(w)≥1 for each vertex v∈V(G), where N[v]={v}∪{u∣uv∈E(G)}. We study a generalization of Dominating Set called Minus Domination (in short, MD) where f:V(G)→{-1,0,1}. Such a function is said to be a minus dominating function if for each vertex v∈V(G), we have ∑w∈N[v]f(w)≥1. The objective is to minimize the weight of a minus domination function, which is f(V)=∑u∈V(G)f(u). The problem is NP-hard even on bipartite, planar, and chordal graphs. In this paper, we study MD from the perspective of parameterized complexity. After observing the complexity of the problem with the natural parameters such as the number of vertices labeled 1, -1 and 0, we study the problem with respect to structural parameters. We show that MD is fixed-parameter tractable when parameterized by twin-cover number, neighborhood diversity or the combined parameters component vertex deletion set and size of the largest component. In addition, we give an XP-algorithm when parameterized by distance to cluster number.Show more - PublicationA Polynomial Kernel for Bipartite Permutation Vertex Deletion(2022-11-01)
;Derbisz, Jan; ;Madathil, Jayakrishnan ;Sahu, Abhishek ;Saurabh, SaketVerma, ShailyShow more In a permutation graph, vertices represent the elements of a permutation, and edges represent pairs of elements that are reversed by the permutation. In the Permutation Vertex Deletion problem, given an undirected graph G and an integer k, the objective is to test whether there exists a vertex subset S⊆ V(G) such that | S| ≤ k and G- S is a permutation graph. The parameterized complexity of Permutation Vertex Deletion is a well-known open problem. Bożyk et al. [IPEC 2020] initiated a study on this problem by requiring that G- S be a bipartite permutation graph (a permutation graph that is bipartite). They called this the Bipartite Permutation Vertex Deletion (BPVD) problem. They showed that the problem admits a factor 9-approximation algorithm as well as a fixed parameter tractable (FPT) algorithm running in time O(9 k| V(G) | 9). Moreover, they posed the question whetherBPVD admits a polynomial kernel. We resolve this question in the affirmative by designing a polynomial kernel for BPVD. In particular, we obtain the following: Given an instance (G, k) of BPVD, in polynomial time we obtain an equivalent instance (G′, k′) of BPVD such that k′≤ k, and | V(G′) | + | E(G′) | ≤ kO(1).Show more - PublicationBurn and Win(2023-01-01)
;Ashok, Pradeesha ;Das, Sayani; ;Saurabh, Saket ;Tomar, AviVerma, ShailyShow more 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 NP-hard even for the union of disjoint paths. Moreover, 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 prove the following results: In this paper, we give an explicit algorithm for the problem parameterized by treewidth, τ and k, that runs in time k2τ4 k5 τnO(1). 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(tlnt) time.We design a kernel of exponential size for Graph Burning in trees.Furthermore, we give an exact algorithm to find the burning number of a graph that runs in time 2 nnO(1), where n is the number of vertices in the input graph.Show more Scopus© Citations 1