6 citations · 14 across the 31 of their papers we have counts for
53 papers
Vertex-Coloring Edge-Weighting: Kernelization and Generalization
Shubhada Aute, Fahad Panolan, Geevarghese Philip
An edge weighting of a graph induces a coloring of its vertices in which the color of a vertex is the total weight of the edges incident with it. Such an edge weighting is proper i…
Counting Paths and Trees via Exterior Algebra
Fahad Panolan, Saket Saurabh, Meirav Zehavi +1
We give randomized approximation algorithms for counting k-paths and k-forests in a host graph. Here k denotes the number of pattern vertices, n and m denote the numbers of host ve…
Fine-Grained Bounds for Courcelle's Theorem
Daniel Lokshtanov, Fahad Panolan, Saket Saurabh +2
Courcelle's theorem states that there exists an algorithm that takes as input a graph of treewidth at most and a MSO formula , and determines whether satisfies i…
Clausal Deletion Backdoors for QBF: a Parameterized Complexity Approach
Leif Eriksson, Victor Lagerkvist, Sebastian Ordyniak +3
Determining the validity of a quantified Boolean formula (QBF) is a PSPACE-complete problem with rich expressive power. Despite interest in efficient solvers, there is, compared to…
Backdoors for Quantified Boolean Formulas
Leif Eriksson, Victor Lagerkvist, Sebastian Ordyniak +3
The quantified Boolean formula problem (QBF) is a well-known PSpace-complete problem with rich expressive power, and is generally viewed as the SAT analogue for PSpace. Given that…
The Parameterized Complexity of Vertex-Coloring Edge-Weighting
Shubhada Aute, Fahad Panolan, Geevarghese Philip
Motivated by the landmark resolution of the 1-2-3 Conjecture, we initiate the study of the parameterized complexity of the Vertex-Coloring {0,1}-Edge-Weighting problem and its gene…
Fast FPT Algorithms for Grundy Number on Dense Graphs
Sina Ghasemi Nezhad, Maryam Moghaddas, Fahad Panolan
In this paper, we investigate the \textsc{Grundy Coloring} problem for graphs with a cluster modulator, a structure commonly found in dense graphs. The Grundy chromatic number, rep…
Parameterized Saga of First-Fit and Last-Fit Coloring
Akanksha Agrawal, Daniel Lokshtanov, Fahad Panolan +2
The classic greedy coloring (first-fit) algorithm considers the vertices of an input graph in a given order and assigns the first available color to each vertex in . In…
Packing Short Cycles
Matthias Bentert, Fedor V. Fomin, Petr A. Golovach +6
Cycle packing is a fundamental problem in optimization, graph theory, and algorithms. Motivated by recent advancements in finding vertex-disjoint paths between a specified set of v…
Subexponential Parameterized Algorithms for Hitting Subgraphs
Daniel Lokshtanov, Fahad Panolan, Saket Saurabh +2
For a finite set of graphs, the -Hitting problem aims to compute, for a given graph (taken from some graph class ) of vertices (and…
Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3
Daniel Lokshtanov, Fahad Panolan, Saket Saurabh +2
In a disk graph, every vertex corresponds to a disk in and two vertices are connected by an edge whenever the two corresponding disks intersect. Disk graphs form an…
When far is better: The Chamberlin-Courant approach to obnoxious committee selection
Sushmita Gupta, Tanmay Inamdar, Pallavi Jain +3
Classical work on metric space based committee selection problem interprets distance as ``near is better''. In this work, motivated by real-life situations, we interpret distance a…
Solving Quantified Boolean Formulas with Few Existential Variables
Leif Eriksson, Victor Lagerkvist, George Osipov +3
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…
Parameterized Algorithms for Minimum Sum Vertex Cover
Shubhada Aute, Fahad Panolan
Minimum sum vertex cover of an -vertex graph is a bijection that minimizes the cost . Finding a minimum sum v…
On the Polynomial Kernelizations of Finding a Shortest Path with Positive Disjunctive Constraints
Susobhan Bandopadhyay, Suman Banerjee, Diptapriyo Majumdar +1
We study the SHORTEST PATH problem with positive disjunctive constraints from the perspective of parameterized complexity. For positive disjunctive constraints, there are certain p…
Meta-theorems for Parameterized Streaming Algorithms
Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan +3
The streaming model was introduced to parameterized complexity independently by Fafianie and Kratsch [MFCS14] and by Chitnis, Cormode, Hajiaghayi and Monemizadeh [SODA15]. Subseque…
Efficient Approximation for Subgraph-Hitting Problems in Sparse Graphs and Geometric Intersection Graphs
Zdeněk Dvořák, Daniel Lokshtanov, Fahad Panolan +3
We investigate a fundamental vertex-deletion problem called (Induced) Subgraph Hitting: given a graph and a set of forbidden graphs, the goal is to compute a mini…
A Framework for Approximation Schemes on Disk Graphs
Daniel Lokshtanov, Fahad Panolan, Saket Saurabh +2
We initiate a systematic study of approximation schemes for fundamental optimization problems on disk graphs, a common generalization of both planar graphs and unit-disk graphs. Ou…
Boolean and -Matrix Factorization: From Theory to Practice
Fedor Fomin, Fahad Panolan, Anurag Patil +1
Boolean Matrix Factorization (BMF) aims to find an approximation of a given binary matrix as the Boolean product of two low-rank binary matrices. Binary data is ubiquitous in many…
Partial Vertex Cover on Graphs of Bounded Degeneracy
Fahad Panolan, Hannane Yaghoubizade
In the Partial Vertex Cover (PVC) problem, we are given an -vertex graph and a positive integer , and the objective is to find a vertex subset of size maximizing…
Deleting, Eliminating and Decomposing to Hereditary Classes Are All FPT-Equivalent
Akanksha Agrawal, Lawqueen Kanesh, Daniel Lokshtanov +4
For a graph class , the graph parameters elimination distance to (denoted by ) [Bulian and Dawar, Algorithmica, 2016], and -treewi…
Gerrymandering on graphs: Computational complexity and parameterized algorithms
Sushmita Gupta, Pallavi Jain, Fahad Panolan +2
Partitioning a region into districts to favor a particular candidate or a party is commonly known as gerrymandering. In this paper, we investigate the gerrymandering problem in gra…
Diverse Collections in Matroids and Graphs
Fedor V. Fomin, Petr A. Golovach, Fahad Panolan +2
We investigate the parameterized complexity of finding diverse sets of solutions to three fundamental combinatorial problems, two from the theory of matroids and the third from gra…
EPTAS for -means Clustering of Affine Subspaces
Eduard Eiben, Fedor V. Fomin, Petr A. Golovach +3
We consider a generalization of the fundamental -means clustering for data with incomplete or corrupted entries. When data objects are represented by points in , a…