Kanesh, Lawqueen

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.

In the Feedback Vertex Set in Tournaments (FVST) problem, we are given a tournament T and a positive integer k. The objective is to determine whether there exists a vertex set X ⊆ V (T) of size at most k such that T − X is a directed acyclic graph. This problem is known to be equivalent to the problem of hitting all directed triangles, thereby using the best-known algorithm for the 3-Hitting Set problem results in an algorithm for FVST with a running time of 2.076k · nO(1) [Wahlström, Ph.D. Thesis]. Kumar and Lokshtanov [STACS 2016] designed a more efficient algorithm with a running time of 1.6181k · nO(1). A generalization of FVST, called Subset-FVST, includes an additional subset S ⊆ V (T) in the input. The goal for Subset-FVST is to find a vertex set X ⊆ V (T) of size at most k such that T − X contains no directed cycles that pass through any vertex in S. This generalized problem can also be represented as a 3-Hitting Set problem, leading to a running time of 2.076k · nO(1). Bai and Xiao [Theoretical Computer Science 2023] improved this and obtained an algorithm with running time 2k+o(k) · nO(1). In our work, we extend the algorithm of Kumar and Lokshtanov [STACS 2016] to solve Subset-FVST, obtaining an algorithm with a running time O(1.6181k + nO(1)), matching the running time for FVST.

Classical vertex subset problems demanding connectivity are of the following form: given an input graph G on n vertices and an integer k, find a set S of at most k vertices that satisfies a property and G[S] is connected. In this paper, we initiate a systematic study of such problems under a specific connectivity constraint, from the viewpoint of Kernelization (Parameterized) Complexity. The specific form that we study does not demand that G[S] is connected but rather G[S] has a closed walk containing all the vertices in S. In particular, we study Closed Walk-Subgraph Vertex Cover (CW-SVC, in short), where given a graph G, a set X⊆ E(G), and an integer k; the goal is to find a set of vertices S that hits all the edges in X and can be traversed by a closed walk of length at most k in G. When X is E(G), this corresponds to Closed Walk-Vertex Cover (CW-VC, in short). One can similarly define these variants for Feedback Vertex Set, namely Closed Walk-Subgraph Feedback Vertex Set (CW-SFVS, in short) and Closed Walk-Feedback Vertex Set (CW-FVS, in short). Our results are as follows: CW-VC and CW-SVC both admit a polynomial kernel, in contrast to Connected Vertex Cover that does not admit a polynomial kernel unless NP⊆ coNP/ poly.CW-FVS admits a polynomial kernel. On the other hand CW-SFVS does not admit even a polynomial Turing kernel unless the polynomial-time hierarchy collapses. We complement our kernelization algorithms by designing single-exponential FPT algorithms – 2 O(k)nO(1) – for all the problems mentioned above.

d-Hitting Set and d-Set Cover are among the classical NP-hard problems. In this paper, we study variants of d-Hitting Set and d-Set Cover, which are called Partial d -Hitting Set (Partial d -HS) and Partial d -Exact Set Cover (Partial d -Exact SC), respectively. In Partial d -HS, given a universe U, a family F, of sets of size at most d over U, and integers k and t, the objective is to decide if there exists a (Formula Presented) of size at most k such that S intersects with at least t sets in F. We obtain a kernel for Partial d -HS in which the size of the universe is bounded by O(dt) and the size of the family is bounded by O(dt2). Using this result, we obtain a kernel for Partial Vertex Cover (PVC) with O(t) vertices, where t is the number of edges to be covered. Next, we study the Partial d -Exact SC problem, where, given a universe U, a family F, of sets of size exactly d over U, and integers k and t, the objective is to decide if there is (Formula Presented) of size at most k, such that S covers at least t elements in U. We design a kernel for Partial d -Exact SC in which sizes of the universe and the family are bounded by (Formula Presented). Finally, we study a special case of Partial d -HS, when d=2, and design an exact exponential time algorithm with running time (Formula Presented).

In this paper, we introduce a directed variant of the classical Bandwidthproblem and study it from the view-point of moderately exponential time algorithms, both exactly and approximately. Motivated by the definitions of the directed variants of the classical Cutwidth and Pathwidth problems, we define Digraph Bandwidth as follows. Given a digraph D and an ordering σ of its vertices, the digraph bandwidth of σ with respect to D is equal to the maximum value of σ(v)-σ(u) over all arcs (u,v) of D going forward along σ (that is, when σ(u)<σ(v)). The Digraph Bandwidth problem takes as input a digraph D and asks to output an ordering with the minimum digraph bandwidth. The undirected Bandwidtheasily reduces to Digraph Bandwidth and thus, it immediately implies that Digraph Bandwidth is NP-hard. While an O⋆(n!) time algorithm for the problem is trivial, the goal of this paper is to design algorithms for Digraph Bandwidth which have running times of the form 2O(n). In particular, we obtain the following results. Here, n and m denote the number of vertices and arcs of the input digraph D, respectively. Digraph Bandwidth can be solved in O⋆(3n·2m) time. This result implies a 2O(n) time algorithm on sparse graphs, such as graphs of bounded average degree (planar graphs). Let G be the underlying undirected graph of the input digraph. If the treewidth of G is at most t, then Digraph Bandwidth can be solved in time O⋆(2n+(t+2)logn). This result implies a 2n+O(nlogn) algorithm, for directed planar graphs and, in general, for the class of digraphs whose underlying undirected graph excludes some fixed graph H as a minor. Digraph Bandwidth can be solved in min{O⋆(4n·bn),O⋆(4n·2blogblogn)} time, where b denotes the optimal digraph bandwidth of D. This allow us to deduce a 2O(n) algorithm in many cases, for example when b≤nlog2n. Finally, we give a (Single) Exponential Time Approximation Scheme for Digraph Bandwidth. In particular, we show that for any fixed real ϵ>0, we can find an ordering whose digraph bandwidth is at most (1+ϵ) times the optimal digraph bandwidth, in time O⋆(4n·(⌈4/ϵ⌉)n). © The Author(s) 2025.

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. © 2024 Elsevier Inc.

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.

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.

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 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 CC-MAX-SAT on Kd,d-free formulas and design an O(d4d2td+1) kernel. © 2025 Elsevier B.V.