Pranabendu Misra

MFCS Conference 2025 Conference Paper

Quasipolynomial-Time Deterministic Kernelization and (Gammoid) Representation

• Rohit Gurjar
• Daniel Lokshtanov
• Pranabendu Misra
• Fahad Panolan
• Saket Saurabh 0001
• Meirav Zehavi

In this paper, we suggest to extend the notion of a kernel to permit the kernelization algorithm to be executed in quasi-polynomial time rather than polynomial time. So far, we are only aware of one work that addressed this negatively, showing that some lower bounds on kernel sizes proved for kernelization also hold when quasi-polynomial time complexity is allowed. When we, anyway, deal with an NP-hard problem, sacrificing polynomial time in preprocessing for quasi-polynomial time may often not be a big deal, but, of course, the question is - does it give us more power? The only known work, mentioned above, seems to suggest that the answer is "no". In this paper, we show that this is not the case - in particular, we show that this notion is extremely powerful for derandomization. Some of the most basic kernelization algorithms in the field are based on inherently randomized tools whose derandomization is a huge problem that has remained (and may still remain) open for many decades. Still, some breakthrough advances for derandomization in quasi-polynomial time have been made. Can we harness these advancements to design quasi-polynomial deterministic kernelization algorithms for basic problems in the field? To this end, we revisit the question of deterministic polynomial-time computation of a linear representation of transversal matroids and gammoids, which is a longstanding open problem. We present a deterministic computation of a representation matrix of a transversal matroid in time quasipolynomial in the rank of the matroid, where each entry of the matrix can be represented in quasipolynomial (in the rank of the matroid) bits. As a corollary, we obtain a linear representation of a gammoid in deterministic quasipolynomial time and quasipolynomial bits in the size of the underlying ground set of the gammoid. In turn, as applications of our results, we present deterministic quasi-polynomial time kernels of polynomial size for several central problems in the field.

SODA Conference 2024 Conference Paper

Meta-theorems for Parameterized Streaming Algorithms‡

• Daniel Lokshtanov
• Pranabendu Misra
• Fahad Panolan
• M. S. Ramanujan 0001
• Saket Saurabh 0001
• Meirav Zehavi

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

A single exponential-time FPT algorithm for cactus contraction

• R. Krithika
• Pranabendu Misra
• Prafullkumar Tale

For a collection F of graphs, the F -Contraction problem takes a graph G and an integer k as input and decides if G can be modified to some graph in F using at most k edge contractions. The F -Contraction problem is NP-Complete for several graph classes F. Heggernes et al. (2014) [4] initiated the study of F -Contraction in the realm of parameterized complexity. They showed that it is FPT if F is the set of all trees or the set of all paths. In this paper, we study F -Contraction where F is the set of all cactus graphs and show that we can solve it in 2 O ( k ) ⋅ | V ( G ) | O ( 1 ) time.

SODA Conference 2022 Conference Paper

A Framework for Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs

• Dániel Marx
• Pranabendu Misra
• Daniel Neuen
• Prafullkumar Tale

Subexponential parameterized algorithms are known for a wide range of natural problems on planar graphs, but the techniques are usually highly problem specific. The goal of this paper is to introduce a framework for obtaining time algorithms for a family of graph modification problems that includes problems that can be seen as generalized cycle hitting problems. Our starting point is the Node U nique L abel C over problem (that is, given a CSP instance where each constraint is a permutation of values on two variables, the task is to delete k variables to make the instance satisfiable). We introduce a variant of the problem where k vertices have to be deleted such that every 2-connected component of the remaining instance is satisfiable. Then we extend the problem with cardinality constraints that restrict the number of times a certain value can be used (globally or within a 2-connected component of the solution). We show that there is an time algorithm on planar graphs for any problem that can be formulated this way, which includes a large number of well-studied problems, for example, O dd C ycle T ransversal, S ubset F eedback V ertex S et, G roup F eedback V ertex S et, S ubset G roup F eedback V ertex S et, V ertex M ultiway C ut, and C omponent O rder C onnectivity. For those problems that admit appropriate (quasi)polynomial kernels (that increase the parameter only linearly and preserve planarity), our results immediately imply time parameterized algorithms on planar graphs. In particular, we use or adapt known kernelization results to obtain time (randomized) algorithms for V ertex M ultiway C ut, G roup F eedback V ertex S et, and S ubset F eedback V ertex S et. Our algorithms are designed with possible generalization to H -minor free graphs in mind. To obtain the same time algorithms on H -minor free graphs, the only missing piece is the vertex version of a contraction decomposition theorem that we currently have only for planar graphs.

SODA Conference 2021 Conference Paper

FPT-approximation for FPT Problems

• Daniel Lokshtanov
• Pranabendu Misra
• M. S. Ramanujan 0001
• Saket Saurabh 0001
• Meirav Zehavi

Over the past decade, many results have focused on the design of parameterized approximation algorithms for W[1]-hard problems. However, there are fundamental problems within the class FPT for which the best known algorithms have seen no progress over the course of the decade; some of them have even been proved not to admit algorithms that run in time 2 ( k ) n (1) under the Exponential Time Hypothesis (ETH) or ( c – ∊ ) k n (1) under the Strong ETH (SETH). In this paper, we expand the study of FPT-approximation and initiate a systematic study of FPT-approximation for problems that are FPT. We design FPT-approximation algorithms for problems that are FPT, with running times that are significantly faster than the corresponding best known FPT-algorithm, and while achieving approximation ratios that are significantly better than what is possible in polynomial time. We present a general scheme to design 2 ( k ) n (1) -time 2-approximation algorithms for cut problems. In particular, we exemplify it for D irected F eedback V ertex S et, D irected S ubset F eedback V ertex S et, D irected O dd C ycle T ransversal and U ndirected M ulticut. Further, we extend our scheme to obtain FPT-time (1)-approximation algorithms for weighted cut problems, where the objective is to obtain a solution of size at most k and of minimum weight. Here, we present two approaches. The first approach achieves 2 ( k ) n (1) -time constant-factor approximation, which we exemplify for all problems mentioned in the first bullet. The other leads to an FPT-approximation Scheme (FPT-AS) for W eighted D irected F eedback V ertex S et. Additionally, we present a combinatorial lemma that yields a partition of the vertex set of a graph to roughly equal sized sets so that the removal of each set reduces its treewidth substantially, which may be of independent interest. For several graph problems, use this lemma to design c w n (1) -time (1 + ∊ )-approximation algorithms that are faster than known SETH lower bounds, where w is the treewidth of the input graph. Examples of such problems include V ertex C over, C omponent O rder C onnectivity, B ounded -D egree V ertex D eletion and ℱ -P acking for any family ℱ of bounded sized graphs. Lastly, we present a general reduction of problems parameterized by treewidth to their versions parameterized by solution size. Combined with our first scheme, we exemplify it to obtain c w n (1) -time bicriteria approximation algorithms for all problems mentioned in the first bullet.

SODA Conference 2021 Conference Paper

Strong Connectivity Augmentation is FPT

• Kristine Vitting Klinkby
• Pranabendu Misra
• Saket Saurabh 0001

Augmenting an undirected or a directed graph (digraph) by adding new edges or arcs, to increase its connectivity to a target value, is a fundamental problem in combinatorial optimization and graph theory. In this paper we study the basic problem of augmenting an input digraph to make it strongly connected, which is known as the S trong C onnectivity A ugmentation problem. Here, the input is a digraph D = ( V, A ), a set of links L ⊆ V × V, and a positive integer k. The objective is to decide if there exists a subset F ⊆ L, of size at most k, such that D′ = ( V, A ∪ F ) is strongly connected. We consider the general version of this problem where, additionally, there is a weight function w: L → ℝ + on the links, and the goal is to find a minimum weight subset F ⊆ L of cardinality at most k, such that D′ = ( V, A ∪ F ) is strongly connected. We design an algorithm for this problem that runs in time 2 ( k log k ) n (1), thereby showing that it is fixed parameter tractable (FPT). Here, n = | V |. This also resolves an open problem stated by Guo and Uhlmann more than a decade ago [ Networks 56 ( 2 ): 131–142 ( 2010 )].

SODA Conference 2020 Conference Paper

2-Approximating Feedback Vertex Set in Tournaments

• Daniel Lokshtanov
• Pranabendu Misra
• Joydeep Mukherjee
• Fahad Panolan
• Geevarghese Philip
• Saket Saurabh 0001

A tournament is a directed graph T such that every pair of vertices is connected by an arc. A feedback vertex set is a set S of vertices in T such that T – S is acyclic. We consider the F eedback V ertex S et problem in tournaments. Here the input is a tournament T and a weight function w: V ( T ) → ℕ and the task is to find a feedback vertex set S in T minimizing w ( S ) = Σ v ϵ S w ( v ). Rounding optimal solutions to the natural LP-relaxation of this problem yields a simple 3-approximation algorithm. This has been improved to 2. 5 by Cai et al. [SICOMP 2000], and subsequently to 7/3 by Mnich et al. [ESA 2016]. In this paper we give the first polynomial time factor 2 approximation algorithm for this problem. Assuming the Unique Games conjecture, this is the best possible approximation ratio achievable in polynomial time.

STOC Conference 2020 Conference Paper

An exponential time parameterized algorithm for planar disjoint paths

• Daniel Lokshtanov
• Pranabendu Misra
• Michal Pilipczuk
• Saket Saurabh 0001
• Meirav Zehavi

In the Disjoint Paths problem, the input is an undirected graph G on n vertices and a set of k vertex pairs, { s i , t i } i =1 k , and the task is to find k pairwise vertex-disjoint paths such that the i ’th path connects s i to t i . In this paper, we give a parameterized algorithm with running time 2 O ( k 2 ) n O (1) for Planar Disjoint Paths, the variant of the problem where the input graph is required to be planar. Our algorithm is based on the unique linkage/treewidth reduction theorem for planar graphs by Adler et al. [JCTB 2017], the algebraic co-homology based technique developed by Schrijver [SICOMP 1994] for Disjoint Paths on directed planar graphs, and one of the key combinatorial insights developed by Cygan et al. [FOCS 2013] in their algorithm for Disjoint Paths on directed planar graphs. To the best of our knowledge our algorithm is the first parameterized algorithm to exploit that the treewidth of the input graph is small in a way completely different from the use of dynamic programming.

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.

MFCS Conference 2020 Conference Paper

Quick Separation in Chordal and Split Graphs

• Pranabendu Misra
• Fahad Panolan
• Ashutosh Rai 0001
• Saket Saurabh 0001
• Roohani Sharma

In this paper we study two classical cut problems, namely Multicut and Multiway Cut on chordal graphs and split graphs. In the Multicut problem, the input is a graph G, a collection of 𝓁 vertex pairs (s_i, t_i), i ∈ [𝓁], and a positive integer k and the goal is to decide if there exists a vertex subset S ⊆ V(G)⧵ {s_i, t_i: i ∈ [𝓁]} of size at most k such that for every vertex pair (s_i, t_i), s_i and t_i are in two different connected components of G-S. In Unrestricted Multicut, the solution S can possibly pick the vertices in the vertex pairs {(s_i, t_i): i ∈ [𝓁]}. An important special case of the Multicut problem is the Multiway Cut problem, where instead of vertex pairs, we are given a set T of terminal vertices, and the goal is to separate every pair of distinct vertices in T× T. The fixed parameter tractability (FPT) of these problems was a long-standing open problem and has been resolved fairly recently. Multicut and Multiway Cut now admit algorithms with running times 2^{{𝒪}(k³)}n^{{𝒪}(1)} and 2^k n^{{𝒪}(1)}, respectively. However, the kernelization complexity of both these problems is not fully resolved: while Multicut cannot admit a polynomial kernel under reasonable complexity assumptions, it is a well known open problem to construct a polynomial kernel for Multiway Cut. Towards designing faster FPT algorithms and polynomial kernels for the above mentioned problems, we study them on chordal and split graphs. In particular we obtain the following results. 1) Multicut on chordal graphs admits a polynomial kernel with {𝒪}(k³ 𝓁⁷) vertices. Multiway Cut on chordal graphs admits a polynomial kernel with {𝒪}(k^{13}) vertices. 2) Multicut on chordal graphs can be solved in time min {𝒪(2^{k} ⋅ (k³+𝓁) ⋅ (n+m)), 2^{𝒪(𝓁 log k)} ⋅ (n+m) + 𝓁 (n+m)}. Hence Multicut on chordal graphs parameterized by the number of terminals is in XP. 3) Multicut on split graphs can be solved in time min {𝒪(1. 2738^k + kn+𝓁(n+m), 𝒪(2^{𝓁} ⋅ 𝓁 ⋅ (n+m))}. Unrestricted Multicut on split graphs can be solved in time 𝒪(4^{𝓁}⋅ 𝓁 ⋅ (n+m)).

SODA Conference 2019 Conference Paper

Interval Vertex Deletion Admits a Polynomial Kernel

• Akanksha Agrawal 0001
• Pranabendu Misra
• Saket Saurabh 0001
• Meirav Zehavi

Given a graph G and an integer k, the I nterval V ertex D eletion (IVD) problem asks whether there exists a subset S ⊆ V ( G ) of size at most k such that G–S is an interval graph. This problem is known to be NP-complete [Yannakakis, STOC’78]. Originally in 2012, Cao and Marx showed that IVD is fixed parameter tractable: they exhibited an algorithm with running time 10 k n O (1) [Cao and Marx, SODA’14]. The existence of a polynomial kernel for IVD remained a well-known open problem in Parameterized Complexity. In this paper, we settle this problem in the affirmative. We also introduce a “bounded intersection” variant of the classical Two Families theorem of Bollobás. We believe this result will find further applications in combinatorics and algorithm design.

SODA Conference 2019 Conference Paper

Popular Matching in Roommates Setting is NP-hard

• Sushmita Gupta
• Pranabendu Misra
• Saket Saurabh 0001
• Meirav Zehavi

SODA Conference 2018 Conference Paper

Parameterized Algorithms for Survivable Network Design with Uniform Demands

• Jørgen Bang-Jensen
• Manu Basavaraju
• Kristine Vitting Klinkby
• Pranabendu Misra
• M. S. Ramanujan 0001
• Saket Saurabh 0001
• Meirav Zehavi

In the S urvivable N etwork D esign P roblem (SNDP), the input is an edge-weighted (di)graph G and an integer r uυ for every pair of vertices u, υ ∊ V ( G ). The objective is to construct a subgraph H of minimum weight which contains r uυ edge-disjoint (or node-disjoint) u-υ paths. This is a fundamental problem in combinatorial optimization that captures numerous well-studied problems in graph theory and graph algorithms. Consequently, there is a long line of research into exact-polynomial time algorithms as well as approximation algorithms for various restrictions of this problem. An important restriction of this problem is one where the connectivity demands are the same for every pair of vertices. In this paper, we first consider the edge-connectivity version of this problem which we call λ-E dge C onnected S ubgraph (λ-ECS). In this problem, the input is a λ-edge connected (di)graph G and an integer k and the objective is to check whether G contains a spanning subgraph H that is also λ-edge connected and H excludes at least k edges of G. In other words, we are asked to compute a maximum subset of edges, of cardinality at least k, which may be safely deleted from G without affecting its connectivity. If we replace λ-edge connectivity with λ-vertex connectivity we get the λ-V ertex C onnected S ubgraph (λ-VCS) problem. We show that λ-ECS is fixed-parameter tractable (FPT) for both graphs and digraphs even if the (di)graph has nonnegative real weights on the edges and the objective is to exclude from H, some edges of G whose total weight exceeds a prescribed value. In particular, we design an algorithm for the weighted variant of the problem with running time 2 O ( k log k ) | V ( G )| O (1). We follow up on this result and obtain a polynomial compression for λ-ECS on unweighted graphs. As a direct consequence of our results, we obtain the first FPT algorithm for the parameterized version of the classical M inimum E quivalent G raph (MEG) problem. We also show that λ-Ves is FPT on digraphs; however the problem on undirected graphs remains open. Finally, we complement our algorithmic findings by showing that SNDP is W[1]-hard for both arc and vertex connectivity versions on digraphs. The core of our algorithms is composed of new combinatorial results on connectivity in digraphs and undirected graphs.

SODA Conference 2017 Conference Paper

Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion

• Akanksha Agrawal 0001
• Daniel Lokshtanov
• Pranabendu Misra
• Saket Saurabh 0001
• Meirav Zehavi

Given a graph G and a parameter k, the C hordal V ertex D eletion (CVD) problem asks whether there exists a subset U ⊆ V ( G ) of size at most k that hits all induced cycles of size at least 4. The existence of a polynomial kernel for CVD was a well-known open problem in the field of Parameterized Complexity. Recently, Jansen and Pilipczuk resolved this question affirmatively by designing a polynomial kernel for CVD of size O ( k 161 log 58 k ), and asked whether one can design a kernel of size O ( k 10 ). While we do not completely resolve this question, we design a significantly smaller kernel of size O ( k 25 log 14 k ), inspired by the O ( k 2 )-size kernel for F eedback V ertex S et. To obtain this result, we first design an O (opt-log 2 n )-factor approximation algorithm for CVD, which is central to our kernelization procedure. Thus, we improve upon both the kernelization algorithm and the approximation algorithm of Jansen and Pilipczuk. Next, we introduce the notion of the independence degree of a vertex, which is our main conceptual contribution. We believe that this notion could be useful in designing kernels for other problems.

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.