Saket Saurabh

TCS Journal 2026 Journal Article

Balanced substructures in bicolored graphs

• P.S. Ardra
• R. Krithika
• Saket Saurabh
• Roohani Sharma

An edge-colored graph is said to be balanced if it has an equal number of edges of each color. Given a graph $G$ whose edges are colored using two colors and a positive integer $k$, the objective in the Edge Balanced Connected Subgraph problem is to determine if $G$ has a balanced connected subgraph containing at least $k$ edges. We first show that this problem is NP-complete and remains so even if the solution is required to be a tree or a path. Then, we focus on the parameterized complexity of Edge Balanced Connected Subgraph and its variants (where the balanced subgraph is required to be a path/tree) with respect to $k$ as the parameter. Towards this, we show that if a graph has a balanced connected subgraph/tree/path of size at least $k$, then it has one of size at least $k$ and at most $f(k)$ where $f$ is a linear function. We use this result combined with dynamic programming algorithms based on color coding and representative sets to show that Edge Balanced Connected Subgraph and its variants are FPT. Further, using polynomial-time reductions to the Multilinear Monomial Detection problem, we give faster randomized FPT algorithms for the problems. In order to describe these reductions, we define a combinatorial object called relaxed-subgraph. We define this object in such a way that balanced connected subgraphs, trees and paths are relaxed-subgraphs with certain properties. This object is defined in the spirit of branching walks known for the Steiner Tree problem and may be of independent interest.

TCS Journal 2026 Journal Article

The parameterized complexity landscape of two-sets cut-uncut

• Matthias Bentert
• Fedor V. Fomin
• Fanny Hauser
• Saket Saurabh

In Two-Sets Cut-Uncut, we are given an undirected graph G = ( V, E ) and two terminal sets S and T. The task is to find a minimum cut C in G (if there is any) separating S from T under the following “uncut” condition. In the graph (V, E∖C), the terminals in each terminal set remain in the same connected component. In spite of the superficial similarity to the classic problem Minimum s-t-Cut, Two-Sets Cut-Uncut is computationally challenging. In particular, even deciding whether such a cut of any size exists, is already NP-complete. We initiate a systematic study of Two-Sets Cut-Uncut within the context of parameterized complexity. By leveraging known relations between many well-studied graph parameters, we characterize the structural properties of input graphs that allow for polynomial kernels, fixed-parameter tractability (FPT), and slicewise polynomial algorithms (XP). Our main contribution is the near-complete establishment of the complexity of these algorithmic properties within the described hierarchy of graph parameters. On a technical level, our main results are fixed-parameter tractability for the (vertex-deletion) distance to cographs and an OR-cross composition excluding polynomial kernels for the vertex cover number of the input graph (under the standard complexity assumption NP ¬ ⊆ coNP/poly).

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.

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.

TCS Journal 2025 Journal Article

Further parameterized results on weak Grundy coloring

• Karthika D
• Muthucumaraswamy R
• Sriram Bhyravarapu
• Satyabrata Jana
• Saket Saurabh

A graph G has a weak Grundy coloring with at least t colors if there exists a surjective function ϕ: V ( G ) → [ t ] = { 1, …, t } that assigns a color from the set [ t ] to each vertex in G such that the following condition holds: for every vertex v ∈ V ( G ) and for every positive integer c < ϕ ( v ), there exists a vertex u such that ϕ ( u ) = c and u v ∈ E ( G ). Given a graph G and t ∈ N, the Weak Grundy Coloring problem asks whether G admits a weak Grundy coloring with at least t colors. In this work, we study this problem in the realm of parameterized complexity with respect to several structural parameters. In particular, we show the following for Weak Grundy Coloring – a 2 O ( k 2 ) ⋅ n O ( 1 ) time algorithm on Clique + k v. – a 2 O ( k 3 ) ⋅ n O ( 1 ) time algorithm parameterized by twin-cover number k, – NP-completeness on Split + 1 v.

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.

IJCAI Conference 2025 Conference Paper

More Efforts Towards Fixed-Parameter Approximability of Multiwinner Rules

• Sushmita Gupta
• Pallavi Jain
• Souvik Saha
• Saket Saurabh
• Anannya Upasana

Multiwinner Elections have emerged as a prominent area of research with numerous practical applications. Given a set of candidates, C, a set of voters, V, approving a subset of candidates (called approval set of a voter), and an integer k, we consider the problem of selecting a ``good'' committee using Thiele rules. This problem is computationally challenging for most Thiele rules with monotone submodular satisfaction functions, as there is no (1-1/e- epsilon) approximation algorithm in f(k)(|C| + |V|)^(o(k)) time for any fixed epsilon > 0 and any computable function f, and no PTAS even when the length of approval set is two. Skowron designed an approximation scheme running in FPT time parameterized by the combined parameter, size of the approval set, and k. In this paper, we consider a parameter d+k (no d voters approve the same set of d candidates), where d is upper bounded by the size of the approval set (thus, can be much smaller). With respect to this parameter, we design parameterized approximation schemes, a lossy polynomial-time preprocessing method, and show that an extra committee member suffices to achieve the desired score (i. e. , 1-additive approximation). Additionally, we resolve an open question by Yang and Wang regarding the fixed-parameter tractability of the problem under the PAV rule with the total score as the parameter, demonstrating that it admits an FPT algorithm.

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.

TCS Journal 2024 Journal Article

Partitioning subclasses of chordal graphs with few deletions

• Satyabrata Jana
• Souvik Saha
• Abhishek Sahu
• Saket Saurabh
• Shaily Verma

In the (Vertex) k -Way Cut problem, input is an undirected graph G, an integer s, and the goal is to find a subset S of edges (vertices) of size at most s, such that G − S has at least k connected components. Downey et al. [Electr. Notes Theor. Comput. Sci. 2003] showed that k -Way Cut is W[1]-hard parameterized by k. However, Kawarabayashi and Thorup [FOCS 2011] showed that the problem is fixed-parameter tractable (FPT) in general graphs with respect to the parameter s and provided a O ( s s O ( s ) n 2 ) time algorithm, where n denotes the number of vertices in G. The best-known algorithm for this problem runs in time s O ( s ) n O ( 1 ) given by Lokshtanov et al. [ACM Tran. of Algo. 2021]. On the other hand, Vertex k -Way Cut is W[1]-hard with respect to either of the parameters, k or s or k + s. These algorithmic results motivate us to look at the problems on special classes of graphs. In this paper, we consider the (Vertex) k -Way Cut problem on subclasses of chordal graphs and obtain the following results. • We first give a sub-exponential FPT algorithm for k -Way Cut running in time 2 O ( s log ⁡ s ) n O ( 1 ) on chordal graphs. • It is “known” that Vertex k -Way Cut is W[1]-hard on chordal graphs, in fact on split graphs, parameterized by k + s. We complement this hardness result by designing polynomial-time algorithms for Vertex k -Way Cut on interval graphs, circular-arc graphs and permutation graphs.

JAIR Journal 2023 Journal Article

Clustering what Matters: Optimal Approximation for Clustering with Outliers

• Akanksha Agrawal
• Tanmay Inamdar
• Saket Saurabh
• Jie Xue

Clustering with outliers is one of the most fundamental problems in Computer Science. Given a set X of n points and two numbers k, m, the clustering with outliers aims to exclude m points from X and partition the remaining points into k clusters that minimizes a certain cost function. In this paper, we give a general approach for solving clustering with outliers, which results in a fixed-parameter tractable (FPT) algorithm in k and m—i.e., an algorithm with running time of the form f(k, m) · nO(1) for some function f—that almost matches the approximation ratio for its outlier-free counterpart. As a corollary, we obtain FPT approximation algorithms with optimal approximation ratios for k-Median and k-Means with outliers in general and Euclidean metrics. We also exhibit more applications of our approach to other variants of the problem that impose additional constraints on the clustering, such as fairness or matroid constraints.

AAAI Conference 2023 Conference Paper

Clustering What Matters: Optimal Approximation for Clustering with Outliers

• Akanksha Agrawal
• Tanmay Inamdar
• Saket Saurabh
• Jie Xue

Clustering with outliers is one of the most fundamental problems in Computer Science. Given a set X of n points and two numbers k and m, the clustering with outliers aims to exclude m points from X, and partition the remaining points into k clusters that minimizes a certain cost function. In this paper, we give a general approach for solving clustering with outliers, which results in a fixed-parameter tractable (FPT) algorithm in k and m (i.e., an algorithm with running time of the form f(k, m) * poly(n) for some function f), that almost matches the approximation ratio for its outlier-free counterpart. As a corollary, we obtain FPT approximation algorithms with optimal approximation ratios for k-Median and k-Means with outliers in general and Euclidean metrics. We also exhibit more applications of our approach to other variants of the problem that impose additional constraints on the clustering, such as fairness or matroid constraints.

TCS Journal 2023 Journal Article

Parameterized algorithms for finding highly connected solution

• Ankit Abhinav
• Susobhan Bandopadhyay
• Aritra Banik
• Saket Saurabh

To introduce our question and the parameterization, consider the classical Vertex Cover problem. In this problem, the input is a graph G on n vertices and a positive integer ℓ, and the goal is to find a vertex subset S of size at most ℓ such that G − S is an independent set. Further, we want that G [ S ] is highly connected. That is, G [ S ] should be n − k edge-connected. Clearly, the problem is NP-complete, as substituting k = n − 1, we obtain the Connected Vertex Cover problem. A simple observation also shows that the problem admits an algorithm with running time n O ( k ). Since the problem is polynomial-time solvable for every fixed integer k, a natural parameter is the integer k. In all the problems we consider, the parameter is k, and the goal is to find a solution S of size at most ℓ, such that G [ S ] is n − k edge-connected and G − S satisfies a property. We show that this version of well-known problems such as Vertex Cover, Feedback Vertex Set, Odd Cycle Transversal and Multiway Cut admit an algorithm with running time f ( k ) ⋅ n O ( 1 ), that is, they are FPT with the parameter k. One of our main subroutines to obtain these algorithms is an FPT algorithm for n − k edge connected Steiner Subgraph, which could be of an independent interest. Finally, we also show that such an algorithm is not possible for Multicut.

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.

TCS Journal 2022 Journal Article

Resolute control: Forbidding candidates from winning an election is hard

• Sushmita Gupta
• Sanjukta Roy
• Saket Saurabh
• Meirav Zehavi

We study a set of voting problems where given an election E = ( C, Π V ) (where C is the set of candidates and Π V is a set of votes), and a non-empty subset of candidates J, the question under consideration is: Can we modify the election in a way so that none of the candidates in J wins the election? The modification operations allowed are that of either adding or deleting some candidates. Yang and Wang (2017) [44] introduced these problems as the Resolute Control problem, a generalization of the destructive control problem where J is a singleton. They studied parameterized complexity of Resolute Control for voting rules Borda (both addition and deletion), Maximin (addition), and Copeland (both addition and deletion). They primarily consider | J | as parameter. In this paper we study Resolute Control parameterized by the other natural parameters viz. , the number of candidates added or deleted. We show that the Resolute Control for Borda (both addition and deletion), Maximin (addition) and Copeland (deletion) are W[2]-hard. We complement this by showing that when the number of voters is odd, Copeland (deletion) is FPT parameterized by the sum of the number of deleted candidates and the size of the feedback arc set of the majority graph of the election.

TCS Journal 2021 Journal Article

Balanced stable marriage: How close is close enough?

• Sushmita Gupta
• Sanjukta Roy
• Saket Saurabh
• Meirav Zehavi

Balanced Stable Marriage (BSM) is a central optimization version of the classic Stable Marriage (SM) problem. We study BSM from the viewpoint of Parameterized Complexity. Informally, the input of BSM consists of n men, n women, and an integer k. Each person a has a (sub)set of acceptable partners, A ( a ), whom a ranks strictly; we use p a ( b ) to denote the position of b ∈ A ( a ) in a's preference list. The objective is to decide whether there exists a stable matching μ such that balance ( μ ) ≜ max ⁡ { ∑ ( m, w ) ∈ μ p m ( w ), ∑ ( m, w ) ∈ μ p w ( m ) } ≤ k. In SM, all stable matchings match the same set of agents, A ⋆ which can be computed in polynomial time. As balance ( μ ) ≥ | A ⋆ | 2 for any stable matching μ, BSM is trivially fixed-parameter tractable (FPT) with respect to k. Thus, a natural question is whether BSM is FPT with respect to k − | A ⋆ | 2. With this viewpoint in mind, we draw a line between tractability and intractability in relation to the target value. This line separates additional natural parameterizations higher/lower than ours (e. g. , we automatically resolve the parameterization k − | A ⋆ | 2 ). The two extreme stable matchings are the man-optimal μ M and the woman-optimal μ W. Let O M = ∑ ( m, w ) ∈ μ M p m ( w ), and O W = ∑ ( m, w ) ∈ μ W p w ( m ). In this work, we prove that • BSM parameterized by t = k − min ⁡ { O M, O W } admits (1) a kernel where the number of people is linear in t, and (2) a parameterized algorithm whose running time is single exponential in t. • BSM parameterized by t = k − max ⁡ { O M, O W } is W[1]-hard.

IJCAI Conference 2021 Conference Paper

Even More Effort Towards Improved Bounds and Fixed-Parameter Tractability for Multiwinner Rules

• Sushmita Gupta
• Pallavi Jain
• Saket Saurabh
• Nimrod Talmon

Multiwinner elections have proven to be a fruitful research topic with many real world applications. We contribute to this line of research by improving the state of the art regarding the computational complexity of computing good committees. More formally, given a set of candidates C, a set of voters V, each ranking the candidates according to their preferences, and an integer k; a multiwinner voting rule identifies a committee of size k, based on these given voter preferences. In this paper we consider several utilitarian and egailitarian OWA (ordered weighted average) scoring rules, which are an extensively researched family of rules (and a subfamily of the family of committee scoring rules). First, we improve the result of Betzler et al. [JAIR, 2013], which gave a O(n^n) algorithm for computing winner under the Chamberlin Courant rule (CC), where n is the number of voters; to a running time of O(2^n), which is optimal. Furthermore, we study the parameterized complexity of the Pessimist voting rule and describe a few tractable and intractable cases. Apart from such utilitarian voting rules, we extend our study and consider egalitarian median and egalitarian mean (both committee scoring rules), showing some tractable and intractable results, based on nontrivial structural observations.

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.

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.

TCS Journal 2020 Journal Article

Fixed-parameter tractable algorithms for Tracking Shortest Paths

• Aritra Banik
• Pratibha Choudhary
• Venkatesh Raman
• Saket Saurabh

We consider the parameterized complexity of the problem of tracking shortest s-t paths in graphs, motivated by applications in security and wireless networks. Given an undirected and unweighted graph with a source s and a destination t, Tracking Shortest Paths asks if there exists a k-sized subset of vertices (referred to as tracking set) that intersects each shortest s-t path in a distinct set of vertices. We first generalize this problem for set systems, namely Tracking Set System, where given a family of subsets of a universe, we are required to find a subset of elements from the universe that has a unique intersection with each set in the family. Tracking Set System is shown to be fixed-parameter tractable due to its relation with a known problem, Test Cover. By a reduction to the well-studied d-hitting set problem, we give a polynomial (with respect to k) kernel for the case when the set sizes are bounded by d. This also helps in solving Tracking Shortest Paths when the input graph diameter is bounded by d. While the results for Tracking Set System show that Tracking Shortest Paths is fixed-parameter tractable, we also give an independent algorithm by using some preprocessing rules, resulting in an improved running time.

TCS Journal 2020 Journal Article

Fully dynamic arboricity maintenance

• Niranka Banerjee
• Venkatesh Raman
• Saket Saurabh

Given an undirected graph, its arboricity is the minimum number of edge disjoint forests that its edge set can be partitioned into. We develop the first fully dynamic algorithms to determine the arboricity of a graph under edge insertions and deletions. While our insertion algorithm is based on known static algorithms to determine the arboricity, our deletion algorithm is, to the best of our knowledge, new. Our algorithms take O ( m log ⁡ n ) time to insert or delete an edge where m is the number of edges in the graph while the best static algorithm to compute arboricity takes O ( m 3 / 2 log ⁡ ( n 2 / m ) ) time [9]. We complement our upper bound with a lower bound of amortized Ω ( log ⁡ n ) time for an update for an algorithm that maintains a forest decomposition of size arboricity of the graph under edge insertions and deletions.

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.

IJCAI Conference 2020 Conference Paper

Well-Structured Committees

• Sushmita Gupta
• Pallavi Jain
• Saket Saurabh

In the standard model of committee selection, we are given a set of ordinal votes over a set of candidates and a desired committee size, and the task is to select a committee that relates to the given votes. Motivated by possible interactions and dependencies between candidates, we study a generalization of committee selection in which the candidates are connected via a network and the task is to select a committee that relates to the given votes while also satisfy certain properties with respect to this candidate network. To accommodate certain correspondences to the voter preferences, we consider three standard voting rules (in particular, $k$-Borda, Chamberlin-Courant, and Gehrlein stability); to model different aspects of interactions and dependencies between candidates, we consider two graph properties (in particular, Independent Set and Connectivity). We study the parameterized complexity of the corresponding combinatorial problems and discuss certain implications of our algorithmic results.

AAMAS Conference 2019 Conference Paper

Gehrlein Stability in Committee Selection: Parameterized Hardness and Algorithms

• Sushmita Gupta
• Pallavi Jain
• Sanjukta Roy
• Saket Saurabh
• Meirav Zehavi

In a multiwinner election based on the Condorcet criterion, we are given a set of candidates, and a set of voters with strict preference ranking over the candidates. A committee is weakly Gehrlein stable (WGS) if each committee member is preferred to each non-member by at least half of the voters. Recently, Aziz et al. [IJCAI 2017] studied the computational complexity of finding a WGS committee of size k. They show that this problem is NP-hard in general and polynomial time solvable when the number of voters is odd. In this article, we initiate a systematic study of the problem in the realm of parameterized complexity. We first show that the problem is W[1]-hard when parameterized by the size of the committee. To overcome this intractability result, we use a known reformulation of WGS as a problem on directed graphs and then use parameters that measure the “structure” of these directed graphs. In particular, we consider the majority graph, defined as follows: there is a vertex corresponding to each candidate, and there is a directed arc from a candidate c to c′ if the number of voters that prefer c over c′ is more than those that prefer c′ over c. The problem of finding WGS committee of size k corresponds to finding a vertex subset X of size k in the majority graph with the following property: the set X contains no vertex outside the committee that has an in-neighbor in X. Observe that the polynomial time algorithm of Aziz et al. [IJCAI 2017] corresponds to solving the problem on a tournament (a complete graph with orientation on edges). Thus, natural parameters to study our problem are “closeness” to being a tournament. We define closeness as the number of missing arcs in the given directed graph and the number of vertices we need to delete from the given directed graph such that the resulting graph is a tournament. We show that the problem is fixed parameter tractable (FPT) and admits linear kernels with respect to closeness parameters. Finally, we also design an exact exponential time algorithm running in time O(1. 2207nnO(1)). Here, n denotes the number of candidates. Proc. of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2019), N. Agmon, M. E. Taylor, E. Elkind, M. Veloso (eds.), May 13–17, 2019, Montreal, Canada. © 2019 International Foundation for Autonomous Agents and Multiagent Systems (www. ifaamas. org). All rights reserved.

IJCAI Conference 2019 Conference Paper

On Succinct Encodings for the Tournament Fixing Problem

• Sushmita Gupta
• Saket Saurabh
• Ramanujan Sridharan
• Meirav Zehavi

Single-elimination tournaments are a popular format in competitive environments. The Tournament Fixing Problem (TFP), which is the problem of finding a seeding of the players such that a certain player wins the resulting tournament, is known to be NP-hard in general and fixed-parameter tractable when parameterized by the feedback arc set number of the input tournament (an oriented complete graph) of expected wins/loses. However, the existence of polynomial kernelizations (efficient preprocessing) for TFP has remained open. In this paper, we present the first polynomial kernelization for TFP parameterized by the feedback arc set number of the input tournament. We achieve this by providing a polynomial-time routine that computes a SAT encoding where the number of clauses is bounded polynomially in the feedback arc set number.

TCS Journal 2019 Journal Article

The parameterized complexity landscape of finding 2-partitions of digraphs

• J. Bang-Jensen
• Kristine V.K. Knudsen
• Saket Saurabh
• Meirav Zehavi

Given a network modeled by a directed graph D = ( V, A ), it is natural to ask whether we can partition the vertex set of D into two disjoint subsets V 1, V 2 (called a 2-partition), such that the digraphs D [ V 1 ], D [ V 2 ] induced by each of these has one of the two properties of interest. This question gives rise to a rich realm of combinatorial problems. The complexity of many such problems was determined in [2, 3]. We analyze a subset of those problems from the viewpoint of parameterized complexity, and present a complete dichotomy of basic, natural properties. More precisely, given a directed graph D = ( V, A ) and two non-negative integers k 1 and k 2, we seek a 2-partition ( V 1, V 2 ) of the vertex set V such that | V 1 | ≥ k 1, | V 2 | ≥ k 2, and each of the subdigraphs induced by V 1 and V 2 has a structural property as defined by the problem at hand—for example, D [ V 1 ] is acyclic and D [ V 2 ] is strongly connected. Specifically, we consider the following eight structural properties: being strongly connected; being connected; having an out-branching; having an in-branching; having minimum degree at least one; having minimum semi-degree at least one; being acyclic; and being complete.

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.

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.

TCS Journal 2018 Journal Article

Parameterized algorithms for stable matching with ties and incomplete lists

• Deeksha Adil
• Sushmita Gupta
• Sanjukta Roy
• Saket Saurabh
• Meirav Zehavi

We study the parameterized complexity of NP-hard optimization versions of Stable Matching and Stable Roommates in the presence of ties and incomplete lists. These problems model many real-life situations where solutions have to satisfy certain predefined criterion of suitability and compatibility. Specifically, our objective is to maximize/minimize the size of the stable matching. Our main theorems state that Stable Matching and Stable Roommates admit small kernels. Consequently, we also conclude that Stable Matching is fixed-parameter tractable (FPT) with respect to solution size, and that Stable Roommates is FPT with respect to a structural parameter. Finally, we analyze the special case where the input graph is planar.

AAMAS Conference 2018 Conference Paper

Stability in Barter Exchange Markets

• Sushmita Gupta
• Fahad Panolan
• Saket Saurabh
• Meirav Zehavi

The notion of stability is the foundation of several classic problems in economics and computer science that arise in a wide-variety of real-world situations, including Stable Marriage, Stable Roommate, Hospital Resident and Group Activity Selection. We study this notion in the context of barter exchange markets. The input of our problem of interest consists of a set of people offering goods/services, with each person subjectively assigning values to a subset of goods/services offered by other people. The goal is to find a stable transaction, a set of cycles that is stable in the following sense: there does not exist a cycle such that every person participating in that cycle prefers to his current “status”. For example, consider a market where families are seeking vacation rentals and offering their own homes for the same. Each family wishes to acquire a vacation home in exchange of its own home without any monetary exchange. We study such a market by analyzing a stable transaction of houses involving cycles of fixed length. The underlying rationale is that an entire trade/exchange fails if any of the participating agents cancels the agreement; as a result, shorter (trading) cycles are desirable. We show that given a transaction, it can be verified whether or not it is stable in polynomial time, and that the problem of finding a stable transaction is NP-hard even if each person desires only a small number of other goods/services. Having established these results, we study the problem of finding a stable transaction in the framework of parameterized algorithms.

IJCAI Conference 2018 Conference Paper

When Rigging a Tournament, Let Greediness Blind You

• Sushmita Gupta
• Sanjukta Roy
• Saket Saurabh
• Meirav Zehavi

A knockout tournament is a standard format of competition, ubiquitous in sports, elections and decision making. Such a competition consists of several rounds. In each round, all players that have not yet been eliminated are paired up into matches. Losers are eliminated, and winners are raised to the next round, until only one winner exists. Given that we can correctly predict the outcome of each potential match (modelled by a tournament D), a seeding of the tournament deterministically determines its winner. Having a favorite player v in mind, the Tournament Fixing Problem (TFP) asks whether there exists a seeding that makes v the winner. Aziz et al. [AAAI’14] showed that TFP is NP-hard. They initiated the study of the parameterized complexity of TFP with respect to the feedback arc set number k of D, and gave an XP-algorithm (which is highly inefficient). Recently, Ramanujan and Szeider [AAAI’17] showed that TFP admits an FPT algorithm, running in time 2^{ O(k^2 log k)} n ^{O(1)}. At the heart of this algorithm is a translation of TFP into an algebraic system of equations, solved in a black box fashion (by an ILP solver). We present a fresh, purely combinatorial greedy solution. We rely on new insights into TFP itself, which also results in the better running time bound of 2^{ O(k log k)} n^{ O(1)}. While our analysis is intricate, the algorithm itself is surprisingly simple.

IJCAI Conference 2018 Conference Paper

Winning a Tournament by Any Means Necessary

• Sushmita Gupta
• Sanjukta Roy
• Saket Saurabh
• Meirav Zehavi

In a tournament, $n$ players enter the competition. In each round, they are paired-up to compete against each other. Losers are thrown, while winners proceed to the next round, until only one player (the winner) is left. Given a prediction of the outcome, for every pair of players, of a match between them (modeled by a digraph $D$), the competitive nature of a tournament makes it attractive for manipulators. In the Tournament Fixing (TF) problem, the goal is to decide if we can conduct the competition (by controlling how players are paired-up) so that our favorite player $w$ wins. A common form of manipulation is to bribe players to alter the outcome of matches. Kim and Williams [IJCAI 2015] integrated such deceit into TF, and showed that the resulting problem is NP-hard when $\ell 0$). For this problem, our contribution is fourfold. First, we present two operations that ``obfuscate deceit'': given one solution, they produce another solution. Second, we present a combinatorial result, stating that there is always a solution with all reversals incident to $w$ and ``elite players''. Third, we give a closed formula for the case where $D$ is a DAG. Finally, we present exact exponential-time and parameterized algorithms for the general case.

TCS Journal 2017 Journal Article

On approximability of optimization problems related to Red/Blue-split graphs

• Sounaka Mishra
• Shijin Rajakrishnan
• Saket Saurabh

An edge-bicolored graph G = ( V, R ∪ B ) is called Red/Blue-split graph if there exists a partition I B and I R of V such that I B and I R are independent sets in ( V, B ) and ( V, R ), respectively. Red/Blue-split graphs generalize several well studied graph classes including split graphs, bipartite graphs and König–Egerváry graphs. In this paper we consider the algorithmic complexity of various optimization problems like minimum edge (or vertex) deletion and maximum edge (or vertex) induced subgraph related to Red/Blue split graphs. All these problems are NP-hard and thus we look at them from algorithmic paradigms that are meant for coping with NP-hardness. We obtain various hardness as well as algorithmic results for these problems in the realm of approximation algorithms and parameterized complexity. The main tool we use to obtain all our results is polynomial time transformations between appropriate problems. On the way, we also resolve some problems related to inapproximability about certain optimization problems mentioned by Korach et al. (2006) [17].

TCS Journal 2017 Journal Article

Parameterized complexity of Strip Packing and Minimum Volume Packing

• Pradeesha Ashok
• Sudeshna Kolay
• S.M. Meesum
• Saket Saurabh

We study the parameterized complexity of Minimum Volume Packing and Strip Packing. In the two dimensional version the input consists of a set of rectangles S with integer side lengths. In the Minimum Volume Packing problem, given a set of rectangles S and a number k, the goal is to decide if the rectangles can be packed in a bounding box of volume at most k. In the Strip Packing problem we are given a set of rectangles S, numbers W and k; the objective is to find if all the rectangles can be packed in a box of dimensions W × k. We prove that the 2-dimensional Volume Packing is in FPT by giving an algorithm that runs in ( 2 ⋅ 2 ) k ⋅ k O ( 1 ) time. We also show that Strip Packing is W[1]-hard even in two dimensions and give an FPT algorithm for a special case of Strip Packing. Some of our results hold for the problems defined in higher dimensions as well.

TCS Journal 2016 Journal Article

Reducing rank of the adjacency matrix by graph modification

• S.M. Meesum
• Pranabendu Misra
• Saket Saurabh

The main topic of this article is to study a class of graph modification problems. A typical graph modification problem takes as input a graph G, a positive integer k and the objective is to add/delete k vertices (edges) so that the resulting graph belongs to a particular family, F, of graphs. In general the family F is defined by forbidden subgraph/minor characterization. In this paper rather than taking a structural route to define F, we take algebraic route. More formally, given a fixed positive integer r, we define F r as the family of graphs where for each G ∈ F r, the rank of the adjacency matrix of G is at most r. Using the family F r we initiate algorithmic study, both in classical and parameterized complexity, of following graph modification problems: r-Rank Vertex Deletion, r-Rank Edge Deletion and r-Rank Editing. These problems generalize the classical Vertex Cover problem and a variant of the d-Cluster Editing problem. We first show that all the three problems are NP-Complete. Then we show that these problems are fixed parameter tractable (FPT) by designing an algorithm with running time 2 O ( k log ⁡ r ) n O ( 1 ) for r-Rank Vertex Deletion, and an algorithm for r-Rank Edge Deletion and r-Rank Editing running in time 2 O ( f ( r ) k log ⁡ k ) n O ( 1 ). We complement our FPT result by designing polynomial kernels for these problems.

TCS Journal 2015 Journal Article

On the parameterized complexity of vertex cover and edge cover with connectivity constraints

• Henning Fernau
• Fedor V. Fomin
• Geevarghese Philip
• Saket Saurabh

We investigate the effect of certain natural connectivity constraints on the parameterized complexity of two fundamental graph covering problems, namely Vertex Cover and Edge Cover. Specifically, we impose the additional requirement that each connected component of a solution have at least t vertices (resp. edges from the solution) for a fixed positive integer t, and call the problem t-Total Vertex Cover (resp. t-Total Edge Cover). In both cases the parameter k is the size of the solution. We show that • both problems remain fixed-parameter tractable with these restrictions, with running times of the form O ⋆ ( c k ) for some constant c > 0 in each case, where the O ⋆ notation hides polynomial factors; • for each fixed t ≥ 2, t-Total Vertex Cover has no polynomial kernel unless CoNP ⊆ NP / poly; • for each fixed t ≥ 2, t-Total Edge Cover has a linear vertex kernel of size t + 1 t k. These results significantly improve earlier work on these problems. We illustrate the utility of the technique used to solve t-Total Vertex Cover, by applying it to derive an O ⋆ ( c k ) -time FPT algorithm for the t-Total Edge Dominating Set problem. Our no-poly-kernel result for t-Total Vertex Cover, and the known NP-hardness result for t-Total Edge Cover, are in stark contrast to the fact that Vertex Cover has a 2k vertex kernel, and that Edge Cover is solvable in polynomial time. This illustrates how even the slightest connectivity requirement results in a drastic change in the tractability of problems—the curse of connectivity!

TCS Journal 2014 Journal Article

Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization

• Mrinal Kumar
• Sounaka Mishra
• N. Safina Devi
• Saket Saurabh

In this paper, we develop approximation algorithms for a few node deletion problems when the input is restricted to be a bipartite graph. We look at node deletion problems for non-trivial properties which can be characterized by forbidden structure which has a bounded intersection with both the bipartitions. The approximation factors obtained directly depend upon the size of the largest such intersection. Special instances of this general problem include problems such as the Minimum Chain Vertex Deletion, Minimum Dissociation Vertex Deletion, Minimum Bipartite Claw Vertex Deletion, Minimum Bi-complement Vertex Deletion and Minimum Bipartite Threshold Vertex Deletion problems. The algorithms are based upon the techniques of linear programming and iterative rounding. We also use the node deletion algorithms to marginally improve the trivial approximation factor for complementary problem of determining the size of the maximum sized vertex induced subgraph lying in the given graph class and prove the APX-completeness of all of these problems.

I&C Journal 2013 Journal Article

Beyond bidimensionality: Parameterized subexponential algorithms on directed graphs

• Frederic Dorn
• Fedor V. Fomin
• Daniel Lokshtanov
• Venkatesh Raman
• Saket Saurabh

In this paper we make the first step beyond bidimensionality by obtaining subexponential time algorithms for problems on directed graphs. We develop two different methods to achieve subexponential time parameterized algorithms for problems on sparse directed graphs. We exemplify our approaches with two well studied problems. For the first problem, k-Leaf Out-Branching, which is to find an oriented spanning tree with at least k leaves, we obtain an algorithm solving the problem in time 2 O ( k log k ) n + n O ( 1 ) on directed graphs whose underlying undirected graph excludes some fixed graph H as a minor. For the special case when the input directed graph is planar, the running time can be improved to 2 O ( k ) n + n O ( 1 ). The second example is a generalization of the Directed Hamiltonian Path problem, namely k-Internal Out-Branching, which is to find an oriented spanning tree with at least k internal vertices. We obtain an algorithm solving the problem in time 2 O ( k log k ) + n O ( 1 ) on directed graphs whose underlying undirected graph excludes some fixed apex graph H as a minor. Finally, we observe that on these classes of graphs, the k-Directed Path problem is solvable in time O ( ( 1 + ε ) k n f ( ε ) ), for any ε > 0, where f is some function of ε. Our methods are based on non-trivial combinations of obstruction theorems for undirected graphs, kernelization, problem-specific combinatorial structures, and a layering technique similar to the one employed by Baker to obtain PTAS for planar graphs.

I&C Journal 2013 Journal Article

Fixed-parameter algorithms for Cochromatic Number and Disjoint Rectangle Stabbing via iterative localization

• Pinar Heggernes
• Dieter Kratsch
• Daniel Lokshtanov
• Venkatesh Raman
• Saket Saurabh

Given a permutation π of { 1, …, n } and a positive integer k, can π be partitioned into at most k subsequences, each of which is either increasing or decreasing? We give an algorithm with running time 2 O ( k 2 log k ) n O ( 1 ) that solves this problem, thereby showing that it is fixed parameter tractable. This NP-complete problem is equivalent to deciding whether the cochromatic number of a given permutation graph on n vertices is at most k. Our algorithm solves in fact a more general problem: within the mentioned running time, it decides whether the cochromatic number of a given perfect graph on n vertices is at most k. To obtain our result we use a combination of two well-known techniques within parameterized algorithms: iterative compression and greedy localization. Consequently we name this combination “iterative localization”. We further demonstrate the power of this combination by giving an algorithm with running time 2 O ( k 2 log k ) n log n that decides whether a given set of n non-overlapping axis-parallel rectangles can be stabbed by at most k of a given set of horizontal and vertical lines.

TCS Journal 2013 Journal Article

Parameterized complexity of MaxSat Above Average

• Robert Crowston
• Gregory Gutin
• Mark Jones
• Venkatesh Raman
• Saket Saurabh

In MaxSat, we are given a CNF formula F with n variables and m clauses; the task is to find a truth assignment satisfying the maximum number of clauses. Let r 1, …, r m be the number of literals in the clauses of F. Then asat ( F ) = ∑ i = 1 m ( 1 − 2 − r i ) is the expected number of clauses satisfied by a random truth assignment, when the truth values to the variables are distributed uniformly and independently. It is well-known that, in polynomial time, one can find a truth assignment satisfying at least asat ( F ) clauses. In the parameterized problem MaxSat-AA, we are to decide whether there is a truth assignment satisfying at least asat ( F ) + k clauses, where k is the (nonnegative) parameter. We prove that MaxSat-AA is para-NP-complete and thus, MaxSat-AA is not fixed-parameter tractable unless P = NP. This is in sharp contrast to the similar problem MaxLin 2-AA which was recently proved to be fixed-parameter tractable by Crowston et al. (FSTTCS 2011). In fact, we consider a more refined version of MaxSat-AA, Max- r ( n ) -Sat-AA, where r j ≤ r ( n ) for each j. Alon et al. (SODA 2010) proved that if r = r ( n ) is a constant, then Max- r -Sat-AA is fixed-parameter tractable. We prove that Max- r ( n ) -Sat-AA is para-NP-complete for any r ( n ) ≥ ⌈ log n ⌉. We also prove that assuming the exponential time hypothesis, Max- r ( n ) -Sat-AA is not even in XP for any integral r ( n ) ≥ log log n + ϕ ( n ), where ϕ ( n ) is any real-valued unbounded strictly increasing computable function. This lower bound on r ( n ) cannot be decreased much further as we prove that Max- r ( n ) -Sat-AA is (i) in XP for any r ( n ) ≤ log log n − log log log n and (ii) fixed-parameter tractable for any r ( n ) ≤ log log n − log log log n − ϕ ( n ), where ϕ ( n ) is any real-valued unbounded strictly increasing computable function. The proof uses some results on MaxLin 2-AA.

AAAI Conference 2012 Conference Paper

Don’t Be Strict in Local Search!

• Serge Gaspers
• Eun Jung Kim
• Sebastian Ordyniak
• Saket Saurabh
• Stefan Szeider

Local Search is one of the fundamental approaches to combinatorial optimization and it is used throughout AI. Several local search algorithms are based on searching the k-exchange neighborhood. This is the set of solutions that can be obtained from the current solution by exchanging at most k elements. As a rule of thumb, the larger k is, the better are the chances of finding an improved solution. However, for inputs of size n, a naı̈ve brute-force search of the k-exchange neighborhood requires nO(k) time, which is not practical even for very small values of k. Fellows et al. (IJCAI 2009) studied whether this brute-force search is avoidable and gave positive and negative answers for several combinatorial problems. They used the notion of local search in a strict sense. That is, an improved solution needs to be found in the k-exchange neighborhood even if a global optimum can be found efficiently. In this paper we consider a natural relaxation of local search, called permissive local search (Marx and Schlotter, IWPEC 2009) and investigate whether it enhances the domain of tractable inputs. We exemplify this approach on a fundamental combinatorial problem, VERTEX COVER. More precisely, we show that for a class of inputs, finding an optimum is hard, strict local search is hard, but permissive local search is tractable. We carry out this investigation in the framework of parameterized complexity.

TCS Journal 2012 Journal Article

On Parameterized Independent Feedback Vertex Set

• Neeldhara Misra
• Geevarghese Philip
• Venkatesh Raman
• Saket Saurabh

We investigate a generalization of the classical Feedback Vertex Set (FVS) problem from the point of view of parameterized algorithms. Independent Feedback Vertex Set (IFVS) is the “independent” variant of the FVS problem and is defined as follows: given a graph G and an integer k, decide whether there exists F ⊆ V ( G ), | F | ≤ k, such that G [ V ( G ) ∖ F ] is a forest and G [ F ] is an independent set; the parameter is k. Note that the similarly parameterized version of the FVS problem–where there is no restriction on the graph G [ F ] –has been extensively studied in the literature. The connected variant CFVS–where G [ F ] is required to be connected–has received some attention as well. The FVS problem easily reduces to the IFVS problem in a manner that preserves the solution size, and so any algorithmic result for IFVS directly carries over to FVS. We show that IFVS can be solved in O ( 5 k n O ( 1 ) ) time, where n is the number of vertices in the input graph G, and obtain a cubic ( O ( k 3 ) ) kernel for the problem. Note the contrast with the CFVS problem, which does not admit a polynomial kernel unless C o N P ⊆ N P / P o l y.

TCS Journal 2011 Journal Article

A Linear Kernel for Planar Connected Dominating Set

• Daniel Lokshtanov
• Matthias Mnich
• Saket Saurabh

We provide polynomial time data reduction rules for Connected Dominating Set on planar graphs and analyze these to obtain a linear kernel for the planar Connected Dominating Set problem. To obtain the desired kernel we introduce a method that we call reduce or refine. Our kernelization algorithm analyzes the input graph and either finds an appropriate reduction rule that can be applied, or zooms in on a region of the graph which is more amenable to reduction. We find this method of independent interest and believe that it will be useful for obtaining linear kernels for other problems on planar graphs.

TCS Journal 2011 Journal Article

An exact algorithm for minimum distortion embedding

• Fedor V. Fomin
• Daniel Lokshtanov
• Saket Saurabh

Let G be an unweighted connected graph on n vertices. We show that an embedding of the shortest path metric of G into the line with minimum distortion can be found in time 5 n + o ( n ). This is the first algorithm breaking the trivial n! -barrier.

TCS Journal 2011 Journal Article

Bandwidth on AT-free graphs

• Petr Golovach
• Pinar Heggernes
• Dieter Kratsch
• Daniel Lokshtanov
• Daniel Meister
• Saket Saurabh

We study the classical Bandwidth problem from the viewpoint of parametrised algorithms. Given a graph G = ( V, E ) and a positive integer k, the Bandwidth problem asks whether there exists a bijective function β: { 1, …, ∣ V ∣ } → V such that for every edge u v ∈ E, ∣ β − 1 ( u ) − β − 1 ( v ) ∣ ≤ k. It is known that under standard complexity assumptions, no algorithm for Bandwidth with running time of the form f ( k ) n O ( 1 ) exists, even when the input is restricted to trees. We initiate the search for classes of graphs where such algorithms do exist. We present an algorithm with running time n ⋅ 2 O ( k log k ) for Bandwidth on AT-free graphs, a well-studied graph class that contains interval, permutation, and cocomparability graphs. Our result is the first non-trivial algorithm that shows fixed-parameter tractability of Bandwidth on a graph class on which the problem remains NP -complete.

I&C Journal 2011 Journal Article

On the complexity of some colorful problems parameterized by treewidth

• Michael R. Fellows
• Fedor V. Fomin
• Daniel Lokshtanov
• Frances Rosamond
• Saket Saurabh
• Stefan Szeider
• Carsten Thomassen

In this paper, we study the complexity of several coloring problems on graphs, parameterized by the treewidth of the graph. 1. The List Coloring problem takes as input a graph G, together with an assignment to each vertex v of a set of colors C v. The problem is to determine whether it is possible to choose a color for vertex v from the set of permitted colors C v, for each vertex, so that the obtained coloring of G is proper. We show that this problem is W [ 1 ] -hard, parameterized by the treewidth of G. The closely related Precoloring Extension problem is also shown to be W [ 1 ] -hard, parameterized by treewidth. 2. An equitable coloring of a graph G is a proper coloring of the vertices where the numbers of vertices having any two distinct colors differs by at most one. We show that the problem is hard for W [ 1 ], parameterized by the treewidth plus the number of colors. We also show that a list-based variation, List Equitable Coloring is W [ 1 ] -hard for forests, parameterized by the number of colors on the lists. 3. The list chromatic number χ l ( G ) of a graph G is defined to be the smallest positive integer r, such that for every assignment to the vertices v of G, of a list L v of colors, where each list has length at least r, there is a choice of one color from each vertex list L v yielding a proper coloring of G. We show that the problem of determining whether χ l ( G ) ⩽ r, the List Chromatic Number problem, is solvable in linear time on graphs of constant treewidth.

AAAI Conference 2010 Conference Paper

Fast Local Search Algorithm for Weighted Feedback Arc Set in Tournaments

• Fedor Fomin
• Daniel Lokshtanov
• Venkatesh Raman
• Saket Saurabh

TCS Journal 2010 Journal Article

Iterative compression and exact algorithms

• Fedor V. Fomin
• Serge Gaspers
• Dieter Kratsch
• Mathieu Liedloff
• Saket Saurabh

Iterative compression has recently led to a number of breakthroughs in parameterized complexity. Here, we show that the technique can also be useful in the design of exact exponential time algorithms to solve NP-hard problems. We exemplify our findings with algorithms for the Maximum Independent Set problem, a parameterized and a counting version of d -Hitting Set and the Maximum Induced Cluster Subgraph problem.

IJCAI Conference 2009 Conference Paper

• Michael R. Fellows
• Frances A. Rosamond
• Fedor V. Fomin
• Daniel Lokshtanov
• Saket Saurabh
• Yngve Villanger

Many local search algorithms are based on searching in the k-exchange neighborhood. This is the set of solutions that can be obtained from the current solution by exchanging at most k elements. As a rule of thumb, the larger k is, the better are the chances of finding an improved solution. However, for inputs of size n, a naı̈ve brute-force search of the k-exchange neighborhood requires nO(k) time, which is not practical even for very small values of k. We show that for several classes of sparse graphs, like planar graphs, graphs of bounded vertex degree and graphs excluding some fixed graph as a minor, an improved solution in the k-exchange neighborhood for many problems can be found much more efficiently. Our algorithms run in time O(τ(k) · nc ), where τ is a function depending on k only and c is a constant independent of k. We demonstrate the applicability of this approach on different problems like r-CENTER, VERTEX COVER, ODD CYCLE TRANSVERSAL, MAX-CUT, and MIN-BISECTION. In particular, on planar graphs, all our algorithms searching for a klocal improvement run in time O(2O(k) ·n2 ), which is polynomial for k = O(log n). We also complement the algorithms with complexity results indicating that—brute force search is unavoidable—in more general classes of sparse graphs.

TCS Journal 2006 Journal Article

Parameterized algorithms for feedback set problems and their duals in tournaments

• Venkatesh Raman
• Saket Saurabh

The parameterized feedback vertex (arc) set problem is to find whether there are k vertices (arcs) in a given graph whose removal makes the graph acyclic. The parameterized complexity of this problem in general directed graphs is a long standing open problem. We investigate the problems on tournaments, a well studied class of directed graphs. We consider both weighted and unweighted versions. We also address the parametric dual problems which are also natural optimization problems. We show that they are fixed parameter tractable not just in tournaments but in oriented directed graphs (where there is at most one directed arc between a pair of vertices). More specifically, the dual problem we show fixed parameter tractable are: Given an oriented directed graph, is there a subset of k vertices (arcs) that forms an acyclic directed subgraph of the graph? Our main results include: • an O ( ( 2. 4143 ) k n ω ) 1 1 ω is the exponent of the best matrix multiplication algorithm. algorithm for weighted feedback vertex set problem, and an O ( ( 2. 415 ) k n ω ) algorithm for weighted feedback arc set problem in tournaments; • an O ( ( e 2 k / k ) k k 2 + min { m lg n, n 2 } ) algorithm for the dual of feedback vertex set problem (maximum vertex induced acyclic graph) in oriented directed graphs, and an O ( 4 k k + m ) algorithm for the dual of feedback arc set problem (maximum arc induced acyclic graph) in general directed graphs. We also show that the dual of feedback vertex set is W [ 1 ] —hard in general directed graphs and the feedback arc set problem is fixed parameter tractable in dense directed graphs. Our results are the first non-trivial results for these problems.