Fahad Panolan

TCS Journal 2026 Journal Article

Covering and partitioning of split, chain and cographs with isometric paths

• Dibyayan Chakraborty
• Haiko Müller
• Sebastian Ordyniak
• Fahad Panolan
• Mateusz Rychlicki

Given a graph G, an isometric path cover of a graph is a set of isometric paths that collectively contain all vertices of G. An isometric path cover C of a graph G is also an isometric path partition if no vertex lies in two paths in C. Given a graph G, and an integer k, the objective of Isometric Path Cover (resp. Isometric Path Partition) is to decide whether G has an isometric path cover (resp. partition) of cardinality k. In this paper, we show that Isometric Path Partition is NP-complete even on split graphs, i. e. graphs whose vertex set can be partitioned into a clique and an independent set. In contrast, we show that both Isometric Path Cover and Isometric Path Partition admit polynomial time algorithms on cographs (graphs with no induced P 4) and chain graphs (bipartite graphs with no induced 2K 2).

I&C Journal 2026 Journal Article

On the polynomial kernelizations of finding a shortest path with positive disjunctive constraints

• Susobhan Bandopadhyay
• Suman Banerjee
• Diptapriyo Majumdar
• Fahad Panolan

We study the Shortest Path problem subject to positive binary disjunctive constraints. In positive disjunctive constraints, there are certain pairs of edges such that at least one edge from every pair must be part of every feasible solution. We initiate the study of Shortest Path with binary positive disjunctive constraints in the perspective of parameterized complexity. Formally, the input instance is a simple undirected graph G = ( V, E ), a forcing graph G f = ( E, E ′ ), two vertices s, t ∈ V(G) and an integer k. Note that the vertex set of Gf is the same as the edge set of G. The goal is to find a set S of at most k edges from G such that there is a path from s to t in the subgraph G = ( V, S ) and S is a vertex cover in Gf. In this paper, we consider two different natural parameterizations for this problem. One natural parameter is the solution size, i. e. k which provides polynomial kernelization results. The other natural parameter is structural parameterizations of Gf, i. e. the size of a modulator X ⊆ E ( G ) = V ( G f ) such that G f − X belongs to some hereditary graph class. We discuss the parameterized complexity of this problem under some structural parameterizations.

SODA Conference 2025 Conference Paper

Crossing Number in Slightly Superexponential Time (Extended Abstract)

• Daniel Lokshtanov
• Fahad Panolan
• Saket Saurabh 0001
• Roohani Sharma
• Jie Xue 0003
• Meirav Zehavi

STOC Conference 2025 Conference Paper

Efficiently Finding and Counting Patterns with Distance Constraints in Sparse Graphs

• Daniel Lokshtanov
• Fahad Panolan
• Saket Saurabh 0001
• Jie Xue 0003
• Meirav Zehavi

Graph classes of bounded expansion were introduced by Nešetřil and de Mendez as a general model of structurally sparse graphs, which have received considerable attention from both combinatorial and algorithmic perspectives. A celebrated result of Dvořák et al. [JACM’13] showed that any first-order model checking problem on bounded-expansion graph classes is fixed-parameter tractable. A main drawback of the FPT algorithms resulted from this result is the high dependency of their time complexity on the parameter k : the algorithms run in time at least doubly exponential in k , even when the graph class is of polynomial expansion. It is natural to ask whether there exist FPT algorithms for these problem that run in singly exponential time, i.e., 2 k O (1) n O (1) time. In this paper, we give a new algorithmic framework for a broad family of first-order model checking problems on sparse graphs, which results in algorithms with running time 2 k O (1) · n when the graph class is of exponential expansion (i.e., the expansion is bounded by a singly exponential function). This covers most well-studied instances of bounded-expansion graph classes, in particular, all polynomial-expansion graph classes. Our framework applies to all problems that can be formulated as finding k vertices in a host graph G with certain distance constraints . Furthermore, the framework can be generalized to give (1 ± ε)-approximation algorithms for the counting versions of these problems with running time 2 k O (1) · n (log n /ε) O (1) on exponential-expansion graph classes. In terms of techniques, our framework differs entirely from the one of Dvořák et al. based on centered coloring. We develop various technical components based on the theory of sparse graphs and other tools such as representative sets/functions, tree decomposition, inclusion-exclusion, etc., which are of independent interest. Remarkably, some of our techniques can be applied to even more general graph classes, such as degenerate graph classes. Therefore, as a byproduct, we obtain a (1 ± ε)-approximation algorithm for approximately counting bounded-treewidth induced subgraphs in degenerate graphs with running time k O ( k ) · ( n /ε) O (1) . This resolves (in a much stronger form) an open problem of Bressan and Roth [FOCS’22], which asked whether such an algorithm exists for counting induced k -matching in degenerate graphs.

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.

TCS Journal 2025 Journal Article

On MAX–SAT with cardinality constraint

• Fahad Panolan
• Hannane Yaghoubizade

We consider the weighted MAX–SAT problem with an additional constraint that at most k variables can be set to true. We call this problem k –WMAX–SAT. This problem admits a ( 1 − 1 e ) -factor approximation algorithm in polynomial time [Sviridenko, Algorithmica (2001)] and it is proved that there is no ( 1 − 1 e + ϵ ) -factor approximation algorithm in f ( k ) ⋅ n o ( k ) time for Maximum Coverage, the unweighted monotone version of k –WMAX–SAT [Manurangsi, SODA 2020]. Therefore, we study two restricted versions of the problem in the realm of parameterized complexity. 1. When the input is an unweighted 2–CNF formula (the problem is called k –MAX–2SAT), we design an efficient polynomial-size approximate kernelization scheme. That is, we design a polynomial-time algorithm that given a 2–CNF formula ψ and ϵ > 0, compresses the input instance to a 2–CNF formula ψ ⋆ such that any c-approximate solution of ψ ⋆ can be converted to a c ( 1 − ϵ ) -approximate solution of ψ in polynomial time. 2. When the input is a planar CNF formula, i. e. , the variable-clause incidence graph is a planar graph, we show the following results: • There is an FPT algorithm for k –WMAX–SAT on planar CNF formulas that runs in 2 O ( k ) ⋅ ( C + V ) time. • There is a polynomial-time approximation scheme for k –WMAX–SAT on planar CNF formulas that runs in time 2 O ( 1 ϵ ) ⋅ k ⋅ ( C + V ). The above-mentioned C and V are the number of clauses and variables of the input formula respectively.

SODA Conference 2025 Conference Paper

Packing Short Cycles

• Matthias Bentert
• Fedor V. Fomin
• Petr A. Golovach
• Tuukka Korhonen
• William Lochet
• Fahad Panolan
• M. S. Ramanujan 0001
• Saket Saurabh 0001

TCS Journal 2025 Journal Article

Parameterized algorithms for minimum sum vertex cover

• Shubhada Aute
• Fahad Panolan

A minimum sum vertex cover of an n-vertex graph G is a bijection ϕ: V ( G ) → [ n ] that minimizes the cost ∑ { u, v } ∈ E ( G ) min ⁡ { ϕ ( u ), ϕ ( v ) }. Finding a minimum sum vertex cover of a graph (the MSVC problem) is NP-hard. MSVC is studied well in the realm of approximation algorithms. The best-known approximation factor in polynomial time for the problem is 16/9 [Bansal, Batra, Farhadi, and Tetali, SODA 2021]. Recently, Stankovic [APPROX/RANDOM 2022] proved that achieving an approximation ratio better than 1. 014 for MSVC is NP-hard, assuming the Unique Games Conjecture. We study the MSVC problem from the perspective of parameterized algorithms. The parameters we consider are the size of a minimum vertex cover and the size of a minimum clique modulator of the input graph. We obtain the following results. – MSVC can be solved in 2 2 O ( k ) n O ( 1 ) time, where k is the size of a minimum vertex cover. – MSVC can be solved in f ( k ) ⋅ n O ( 1 ) time for some computable function f, where k is the size of a minimum clique modulator.

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.

STOC Conference 2025 Conference Paper

Subexponential Parameterized Algorithms for Hitting Subgraphs

• Daniel Lokshtanov
• Fahad Panolan
• Saket Saurabh 0001
• Jie Xue 0003
• Meirav Zehavi

MFCS Conference 2024 Conference Paper

Covering and Partitioning of Split, Chain and Cographs with Isometric Paths

• Dibyayan Chakraborty
• Haiko Müller
• Sebastian Ordyniak
• Fahad Panolan
• Mateusz Rychlicki

Given a graph G, an isometric path cover of a graph is a set of isometric paths that collectively contain all vertices of G. An isometric path cover 𝒞 of a graph G is also an isometric path partition if no vertex lies in two paths in 𝒞. Given a graph G, and an integer k, the objective of Isometric Path Cover (resp. Isometric Path Partition) is to decide whether G has an isometric path cover (resp. partition) of cardinality k. In this paper, we show that Isometric Path Partition is NP-complete even on split graphs, i. e. graphs whose vertex set can be partitioned into a clique and an independent set. In contrast, we show that both Isometric Path Cover and Isometric Path Partition admit polynomial time algorithms on cographs (graphs with no induced P₄) and chain graphs (bipartite graphs with no induced 2K₂).

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

IJCAI Conference 2024 Conference Paper

Solving Quantified Boolean Formulas with Few Existential Variables

• Leif Eriksson
• Victor Lagerkvist
• Sebastian Ordyniak
• George Osipov
• Fahad Panolan
• Mateusz Rychlicki

The quantified Boolean formula (QBF) problem is an important decision problem generally viewed as the archetype for PSPACE-completeness. Many problems of central interest in AI are in general not included in NP, e. g. , planning, model checking, and non-monotonic reasoning, and for such problems QBF has successfully been used as a modelling tool. However, solvers for QBF are not as advanced as state of the art SAT solvers, which has prevented QBF from becoming a universal modelling language for PSPACE-complete problems. A theoretical explanation is that QBF (as well as many other PSPACE-complete problems) lacks natural parameters guaranteeing fixed-parameter tractability (FPT). In this paper we tackle this problem and consider a simple but overlooked parameter: the number of existentially quantified variables. This natural parameter is virtually unexplored in the literature which one might find surprising given the general scarcity of FPT algorithms for QBF. Via this parameterization we then develop a novel FPT algorithm applicable to QBF instances in conjunctive normal form (CNF) of bounded clause length. We complement this by a W[1]-hardness result for QBF in CNF of unbounded clause length as well as sharper lower bounds for the bounded arity case under the (strong) exponential-time hypothesis.

SODA Conference 2023 Conference Paper

A Framework for Approximation Schemes on Disk Graphs

• Daniel Lokshtanov
• Fahad Panolan
• Saket Saurabh 0001
• Jie Xue 0003
• Meirav Zehavi

SODA Conference 2023 Conference Paper

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

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

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

SODA Conference 2022 Conference Paper

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

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

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

SODA Conference 2022 Conference Paper

Subexponential Parameterized Algorithms on Disk Graphs (Extended Abstract)

• Daniel Lokshtanov
• Fahad Panolan
• Saket Saurabh 0001
• Jie Xue 0003
• Meirav Zehavi

One of the most celebrated results in Parameterized Complexity is the Bidimensionality theory of Demaine et al. [J. ACM, 2005], which has yielded, over the past two decades, numerous subexponential-time fixed-parameter tractable (FPT) algorithms for various problems on planar (and H -minor-free) graphs. At the heart of this theory is the proof of sublinear bounds in terms of solution size on the treewidth of a given graph. Inspired by this theory, in recent years, significant efforts have been devoted to design subexponential-time FPT algorithms for problems on geometric graph classes that utilize new treewidth bounds, in particular (but not only) for unit disk graphs [Fomin et al. , SODA'12; Fomin et al. , DCG'19; Panolan et al. , SODA'19; Fomin et al. SoCG'20]. In this paper, we aim to attain such results on disk graphs, a broad class of graphs that generalizes both the classes of planar graphs and unit disk graphs, and thereby unify the aforementioned research frontiers for planar and unit disk graphs. Our main contribution is an approach to design subexponential-time FPT algorithms for problems on disk graphs, which we apply to several well-studied graph problems. At the heart of our approach lie two new combinatorial theorems concerning the treewidth of disk graphs having a realization of bounded ply (or maximum clique size) that are of independent interest. In particular, we prove a stronger version of the following treewidth bound: Let G be a disk graph that has some realization of ply p and no false twins, and M ⊆ V(G ) such that G has no triangle with exactly one vertex from M, and G – M has treewidth w. Then, the treewidth of G is. Among our applications are the first subexponential-time FPT algorithms for several problems on disk graphs, including T riangle H itting, F eedback V ertex S et and O dd C ycle T ransversal (OCT). Previously, subexponential-time FPT algorithms for these problems were only known on planar graphs and unit disk graphs (excluding OCT, which was only known to admit such an algorithm on planar graphs). Our algorithms are robust, in particular, they do not require a geometric realization of the input graph (for all aforementioned problems), and they generalize to the weighted and counting versions of all aforementioned problems except for OCT.

SODA Conference 2021 Conference Paper

EPTAS for k -means Clustering of Affine Subspaces

• Eduard Eiben
• Fedor V. Fomin
• Petr A. Golovach
• William Lochet
• Fahad Panolan
• Kirill Simonov

We consider a generalization of the fundamental k -means clustering for data with incomplete or corrupted entries. When data objects are represented by points in ℝ d, a data point is said to be incomplete when some of its entries are missing or unspecified. An incomplete data point with at most Δ unspecified entries corresponds to an axis-parallel affine subspace of dimension at most Δ, called a Δ-point. Thus we seek a partition of n input Δ-points into k clusters minimizing the k -means objective. For Δ = 0, when all coordinates of each point are specified, this is the usual k -means clustering. We give an algorithm that finds an (1 + ∊ )-approximate solution in time f ( k, ∊, Δ) · n 2 · d for some function f of k, ∊, and Δ only.

ICML Conference 2021 Conference Paper

Fixed-Parameter and Approximation Algorithms for PCA with Outliers

• Yogesh Dahiya
• Fedor V. Fomin
• Fahad Panolan
• Kirill Simonov

PCA with Outliers is the fundamental problem of identifying an underlying low-dimensional subspace in a data set corrupted with outliers. A large body of work is devoted to the information-theoretic aspects of this problem. However, from the computational perspective, its complexity is still not well-understood. We study this problem from the perspective of parameterized complexity by investigating how parameters like the dimension of the data, the subspace dimension, the number of outliers and their structure, and approximation error, influence the computational complexity of the problem. Our algorithmic methods are based on techniques of randomized linear algebra and algebraic geometry.

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

Hitting topological minors is FPT

• Fedor V. Fomin
• Daniel Lokshtanov
• Fahad Panolan
• Saket Saurabh 0001
• Meirav Zehavi

In the Topological Minor Deletion (TM-Deletion) problem, the input consists of an undirected graph G , a family of undirected graphs F and an integer k . The task is to determine whether G contains a set of vertices S of size at most k , such that the graph G ∖ S obtained from G by removing the vertices of S , contains no graph from F as a topological minor. We give an algorithm forTM-Deletion with running time f ( h ⋆ , k )· | V ( G )| 4 . Here h ⋆ is the maximum size of a graph in F and f is a computable function of h ⋆ and k . This is the first fixed parameter tractable algorithm (FPT) for the problem. In fact, even for the restricted case of planar inputs the first FPT algorithm was found only recently by Golovach et al. [SODA 2020]. For this case we improve upon the algorithm of Golovach et al. [SODA 2020] by designing an FPT algorithm with explicit dependence on k and h ⋆ .

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.

AAAI Conference 2020 Conference Paper

Manipulating Districts to Win Elections: Fine-Grained Complexity

• Eduard Eiben
• Fedor Fomin
• Fahad Panolan
• Kirill Simonov

Gerrymandering is a practice of manipulating district boundaries and locations in order to achieve a political advantage for a particular party. Lewenberg, Lev, and Rosenschein [AAMAS 2017] initiated the algorithmic study of a geographically-based manipulation problem, where voters must vote at the ballot box closest to them. In this variant of gerrymandering, for a given set of possible locations of ballot boxes and known political preferences of n voters, the task is to identify locations for k boxes out of m possible locations to guarantee victory of a certain party in at least districts. Here integers k and are some selected parameter. It is known that the problem is NP-complete already for 4 political parties and prior to our work only heuristic algorithms for this problem were developed. We initiate the rigorous study of the gerrymandering problem from the perspectives of parameterized and fine-grained complexity and provide asymptotically matching lower and upper bounds on its computational complexity. We prove that the problem is W[1]-hard parameterized by k + n and that it does not admit an f(n, k) · mo( √ k) algorithm for any function f of k and n only, unless the Exponential Time Hypothesis (ETH) fails. Our lower bounds hold already for 2 parties. On the other hand, we give an algorithm that solves the problem for a constant number of parties in time (m + n)O( √ k).

TCS Journal 2020 Journal Article

On the parameterized complexity of [1,j]-domination problems

• Mohsen Alambardar Meybodi
• Fedor V. Fomin
• Amer E. Mouawad
• Fahad Panolan

For a graph G, a set D ⊆ V ( G ) is called a [ 1, j ] -dominating set if every vertex in V ( G ) ∖ D has at least one and at most j neighbors in D. A set D ⊆ V ( G ) is called a [ 1, j ] -total dominating set if every vertex in V ( G ) has at least one and at most j neighbors in D. In the [ 1, j ] -(Total) Dominating Set problem we are given a graph G and a positive integer k. The objective is to test whether there exists a [ 1, j ] -(total) dominating set of size at most k. The [ 1, j ] -Dominating Set problem is known to be NP-complete, even for restricted classes of graphs such as chordal and planar graphs, but polynomial-time solvable on split graphs. The [ 1, 2 ] -Total Dominating Set problem is known to be NP-complete, even for bipartite graphs. As both problems generalize the Dominating Set problem, both are W[1]-hard when parameterized by solution size. In this work, we study the aforementioned problems on various graph classes from the perspective of parameterized complexity and prove the following results: • [ 1, j ] -Dominating Set parameterized by solution size is W[1]-hard on d-degenerate graphs for d = j + 1. • [ 1, j ] -Dominating Set parameterized by solution size is FPT on nowhere dense graphs. • The known algorithm for [ 1, j ] -Dominating Set on split graphs is optimal under the Strong Exponential Time Hypothesis (SETH). • Assuming SETH, we provide a lower bound for the running time of any algorithm solving the [ 1, 2 ] -Total Dominating Set problem parameterized by pathwidth. • Finally, we study another variant of Dominating Set, called Restrained Dominating Set, that asks if there is a dominating set D of G of size at most k such that no vertex outside of D has all of its neighbors in D. We prove this variant is W[1]-hard even on 3-degenerate graphs.

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

Contraction Decomposition in Unit Disk Graphs and Algorithmic Applications in Parameterized Complexity

• Fahad Panolan
• Saket Saurabh 0001
• Meirav Zehavi

We give a new decomposition theorem in unit disk graphs (UDGs) and demonstrate its applicability in the fields of Structural Graph Theory and Parameterized Complexity. First, our new decomposition theorem shows that the class of UDGs admits a Contraction Decomposition Theorem. Prior studies on this topic exhibited that the classes of planar graphs [Klein, SICOMP, 2008], graphs of bounded genus [Demaine, Hajiaghayi and Mohar, Combinatorica 2010] and H -minor free graphs [Demaine, Hajiaghayi and Kawarabayashi, STOC 2011] admit a Contraction Decomposition Theorem. Even bounded-degree UDGs can contain arbitrarily large cliques as minors, therefore our result is a significant advance in the study of contraction decompositions. Additionally, this result answers an open question posed by Hajiaghayi ( www. youtube. com/watch? v=2Bq2gy1N01w ) regarding the existence of contraction decompositions for classes of graphs beyond H -minor free graphs. Second, we present a “parameteric version” of our new decomposition theorem. We prove that there is an algorithm that given a UDG G and a positive integer k, runs in polynomial time and outputs a collection of O ( k ) tree decompositions of G with the following properties. Each bag in any of these tree decompositions can be partitioned into O ( k ) connected pieces (we call this measure the chunkiness of the tree decomposition). Moreover, for any subset S of at most k edges in G, there is a tree decomposition in the collection such that S is well preserved in the decomposition in the following sense. For any bag in the tree decomposition and any edge in S with both endpoints in the bag, either its endpoints lie in different pieces or they lie in a piece which is a clique. Having this decomposition at hand, we show that the design of parameterized algorithms for some cut problems becomes elementary. In particular, our algorithmic applications include single-exponential (or slightly superexponential) algorithms for well-studied problems such as M in B isection, S teiner C ut, s -W ay C ut, and E dge M ultiway C ut -U ncut on UDGs; these algorithms are substantially faster than the best known algorithms for these problems on general graphs.

TCS Journal 2019 Journal Article

Harmonious coloring: Parameterized algorithms and upper bounds

• Sudeshna Kolay
• Ragukumar Pandurangan
• Fahad Panolan
• Venkatesh Raman
• Prafullkumar Tale

A harmonious coloring of a graph is a partitioning of its vertex set into parts such that, there are no edges inside each part, and there is at most one edge between any pair of parts. It is known that finding a minimum harmonious coloring number is NP-hard even in special classes of graphs like trees and split graphs. We initiate a study of parameterized and exact exponential time complexity of harmonious coloring. We consider various parameterizations like by solution size, by above or below known guaranteed bounds and by the vertex cover number of the graph. While the problem has a simple quadratic kernel when parameterized by the solution size, our main result is that the problem is fixed-parameter tractable when parameterized by the size of a vertex cover of the graph. This is shown by reducing the problem to multiple instances of fixed variable integer linear programming. We also observe that it is W [ 1 ] -hard to determine whether at most n − k or Δ + 1 + k colors are sufficient in a harmonious coloring of an n-vertex graph G, where Δ is the maximum degree of G and k is the parameter. Concerning exact exponential time algorithms, we develop a 2 n n O ( 1 ) algorithm for finding a minimum harmonious coloring in split graphs improving on the naive 2 O ( n log ⁡ n ) algorithm.

ICML Conference 2019 Conference Paper

Refined Complexity of PCA with Outliers

• Kirill Simonov
• Fedor V. Fomin
• Petr A. Golovach
• Fahad Panolan

Principal component analysis (PCA) is one of the most fundamental procedures in exploratory data analysis and is the basic step in applications ranging from quantitative finance and bioinformatics to image analysis and neuroscience. However, it is well-documented that the applicability of PCA in many real scenarios could be constrained by an "immune deficiency" to outliers such as corrupted observations. We consider the following algorithmic question about the PCA with outliers. For a set of $n$ points in $\mathbb{R}^{d}$, how to learn a subset of points, say 1% of the total number of points, such that the remaining part of the points is best fit into some unknown $r$-dimensional subspace? We provide a rigorous algorithmic analysis of the problem. We show that the problem is solvable in time $n^{O(d^2)}$. In particular, for constant dimension the problem is solvable in polynomial time. We complement the algorithmic result by the lower bound, showing that unless Exponential Time Hypothesis fails, in time $f(d)n^{o(d)}$, for any function $f$ of $d$, it is impossible not only to solve the problem exactly but even to approximate it within a constant factor.

JAAMAS Journal 2019 Journal Article

Stability in barter exchange markets

• Sushmita Gupta
• Fahad Panolan
• Meirav Zehavi

Abstract 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.

SODA Conference 2018 Conference Paper

Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms

• Daniel Lokshtanov
• Fahad Panolan
• Saket Saurabh 0001
• Roohani Sharma
• Meirav Zehavi

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.

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.

MFCS Conference 2017 Conference Paper

Communication Complexity of Pairs of Graph Families with Applications

• Sudeshna Kolay
• Fahad Panolan
• Saket Saurabh 0001

Given a graph G and a pair (\mathcal{F}_1, \mathcal{F}_2) of graph families, the function {\sf GDISJ}_{G, {\cal F}_1, {\cal F}_2} takes as input, two induced subgraphs G_1 and G_2 of G, such that G_1 \in \mathcal{F}_1 and G_2 \in \mathcal{F}_2 and returns 1 if V(G_1)\cap V(G_2)=\emptyset and 0 otherwise. We study the communication complexity of this problem in the two-party model. In particular, we look at pairs of hereditary graph families. We show that the communication complexity of this function, when the two graph families are hereditary, is sublinear if and only if there are finitely many graphs in the intersection of these two families. Then, using concepts from parameterized complexity, we obtain nuanced upper bounds on the communication complexity of GDISJ_G, \cal F_1, \cal F_2. A concept related to communication protocols is that of a (\mathcal{F}_1, \mathcal{F}_2)-separating family of a graph G. A collection \mathcal{F} of subsets of V(G) is called a (\mathcal{F}_1, \mathcal{F}_2)-separating family} for G, if for any two vertex disjoint induced subgraphs G_1\in \mathcal{F}_1, G_2\in \mathcal{F}_2, there is a set F \in \mathcal{F} with V(G_1) \subseteq F and V(G_2) \cap F = \emptyset. Given a graph G on n vertices, for any pair (\mathcal{F}_1, \mathcal{F}_2) of hereditary graph families with sublinear communication complexity for GDISJ_G, \cal F_1, \cal F_2, we give an enumeration algorithm that finds a subexponential sized (\mathcal{F}_1, \mathcal{F}_2)-separating family. In fact, we give an enumeration algorithm that finds a 2^{o(k)}n^{\Oh(1)} sized (\mathcal{F}_1, \mathcal{F}_2)-separating family; where k denotes the size of a minimum sized set S of vertices such that V(G)\setminus S has a bipartition (V_1, V_2) with G[V_1] \in {\cal F}_1 and G[V_2]\in {\cal F}_2. We exhibit a wide range of applications for these separating families, to obtain combinatorial bounds, enumeration algorithms as well as exact and FPT algorithms for several problems.

STOC Conference 2017 Conference Paper

Lossy kernelization

• Daniel Lokshtanov
• Fahad Panolan
• M. S. Ramanujan 0001
• Saket Saurabh 0001

In this paper we propose a new framework for analyzing the performance of preprocessing algorithms. Our framework builds on the notion of kernelization from parameterized complexity. However, as opposed to the original notion of kernelization, our definitions com- bine well with approximation algorithms and heuristics. The key new definition is that of a polynomial size α-approximate kernel. Loosely speaking, a polynomial size α-approximate kernel is a polynomial time pre-processing algorithm that takes as input an instance ( I , k ) to a parameterized problem, and outputs another instance ( I ′, k ′) to the same problem, such that | I ′| + k ′ ≤ k O (1) . Additionally, for every c ≥ 1, a c -approximate solution s ′ to the pre-processed instance ( I ′, k ′) can be turned in polynomial time into a ( c · α)-approximate solution s to the original instance ( I , k ). Amongst our main technical contributions are α-approximate kernels of polynomial size for three problems, namely Connected Vertex Cover, Disjoint Cycle Packing and Disjoint Factors. These problems are known not to admit any polynomial size kernels unless NP ⊆ coNP / Poly . Our approximate kernels simultaneously beat both the lower bounds on the (normal) kernel size, and the hardness of approximation lower bounds for all three problems. On the negative side we prove that Longest Path parameterized by the length of the path and Set Cover parameterized by the universe size do not admit even an α-approximate kernel of polynomial size, for any α≥1, unless NP ⊆ coNP / Poly . In order to prove this lower bound we need to combine in a non-trivial way the techniques used for showing kernelization lower bounds with the methods for showing hardness of approximation.

MFCS Conference 2016 Conference Paper

Parameterized Algorithms on Perfect Graphs for Deletion to (r, l)-Graphs

• Sudeshna Kolay
• Fahad Panolan
• Venkatesh Raman 0001
• Saket Saurabh 0001

For fixed integers r, l >= 0, a graph G is called an (r, l)-graph if the vertex set V(G) can be partitioned into r independent sets and l cliques. Such a graph is also said to have cochromatic number r+l. The class of (r, l) graphs generalizes r-colourable graphs (when l=0) and hence not surprisingly, determining whether a given graph is an (r, l)-graph is NP-hard even when r >= 3 or l >= 3 in general graphs. When r and ell are part of the input, then the recognition problem is NP-hard even if the input graph is a perfect graph (where the Chromatic Number problem is solvable in polynomial time). It is also known to be fixed-parameter tractable (FPT) on perfect graphs when parameterized by r and l. I. e. there is an f(r+l) n^O(1) algorithm on perfect graphs on n vertices where f is a function of r and l. Observe that such an algorithm is unlikely on general graphs as the problem is NP-hard even for constant r and l. In this paper, we consider the parameterized complexity of the following problem, which we call Vertex Partization. Given a perfect graph G and positive integers r, l, k decide whether there exists a set S subset or equal to V(G) of size at most k such that the deletion of S from G results in an (r, l)-graph. This problem generalizes well studied problems such as Vertex Cover (when r=1 and l=0), Odd Cycle Transversal (when r=2, l=0) and Split Vertex Deletion (when r=1=l). 1. Vertex Partization on perfect graphs is FPT when parameterized by k+r+l. 2. The problem, when parameterized by k+r+l, does not admit any polynomial sized kernel, under standard complexity theoretic assumptions. In other words, in polynomial time, the input graph cannot be compressed to an equivalent instance of size polynomial in k+r+l. In fact, our result holds even when k=0. 3. When r, ell are universal constants, then Vertex Partization on perfect graphs, parameterized by k, has a polynomial sized kernel.

MFCS Conference 2013 Conference Paper

Subexponential Algorithm for d-Cluster Edge Deletion: Exception or Rule?

• Neeldhara Misra
• Fahad Panolan
• Saket Saurabh 0001

Abstract The correlation clustering problem is a fundamental problem in both theory and practice, and it involves identifying clusters of objects in a data set based on their similarity. A traditional modeling of this question as a graph theoretic problem involves associating vertices with data points and indicating similarity by adjacency. Clusters then correspond to cliques in the graph. The resulting optimization problem, Cluster Editing (and several variants) are very well-studied algorithmically. In many situations, however, translating clusters to cliques can be somewhat restrictive. A more flexible notion would be that of a structure where the vertices are mutually “not too far apart”, without necessarily being adjacent. One such generalization is realized by structures called s-clubs, which are graphs of diameter at most s. In this work, we study the question of finding a set of at most k edges whose removal leaves us with a graph whose components are s -clubs. Recently, it has been shown that unless Exponential Time Hypothesis fail (ETH) fails Cluster Editing (whose components are 1-clubs) does not admit sub-exponential time algorithm [ STACS, 2013 ]. That is, there is no algorithm solving the problem in time 2 o ( k ) n O (1). However, surprisingly they show that when the number of cliques in the output graph is restricted to d, then the problem can be solved in time \(O(2^{O(\sqrt{dk})}+m+n)\). We show that this sub-exponential time algorithm for the fixed number of cliques is rather an exception than a rule. Our first result shows that assuming the ETH, there is no algorithm solving the s -Club Cluster Edge Deletion problem in time 2 o ( k ) n O (1). We show, further, that even the problem of deleting edges to obtain a graph with d s -clubs cannot be solved in time 2 o ( k ) n O (1) for any fixed s, d ≥ 2. This is a radical contrast from the situation established for cliques, where sub-exponential algorithms are known.