Fahad Panolan

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 $G$ of treewidth at most $t$ and a MSO formula $ϕ$ , and determines whether $G$ satisfies $ϕ$ i…

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…

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 $F$ of graphs, the $F$ -Hitting problem aims to compute, for a given graph $G$ (taken from some graph class $G$ ) of $n$ 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 $R^{2}$ 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…

Parameterized Algorithms for Minimum Sum Vertex Cover

Shubhada Aute, Fahad Panolan

Minimum sum vertex cover of an $n$ -vertex graph $G$ is a bijection $ϕ : V (G) \to [n]$ that minimizes the cost $\sum_{{u, v} \in E (G)} min {ϕ (u), ϕ (v)}$ . Finding a minimum sum v…

cs.DS2023

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…

cs.DS2023

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 $G$ and a set $F$ of forbidden graphs, the goal is to compute a mini…

cs.DS2022

Partial Vertex Cover on Graphs of Bounded Degeneracy

Fahad Panolan, Hannane Yaghoubizade

In the Partial Vertex Cover (PVC) problem, we are given an $n$ -vertex graph $G$ and a positive integer $k$ , and the objective is to find a vertex subset $S$ of size $k$ maximizing…

cs.DS2021★ 1 cited

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

Akanksha Agrawal, Lawqueen Kanesh, Daniel Lokshtanov +4

For a graph class $H$ , the graph parameters elimination distance to $H$ (denoted by $ed_{H}$ ) [Bulian and Dawar, Algorithmica, 2016], and $H$ -treewi…

cs.DS2021

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…

cs.DS2021

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 $k$ -means Clustering of Affine Subspaces

Eduard Eiben, Fedor V. Fomin, Petr A. Golovach +3

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 $R^{d}$ , a…

Improved FPT Algorithms for Deletion to Forest-like Structures

Kishen N. Gowda, Aditya Lonkar, Fahad Panolan +2

The Feedback Vertex Set problem is undoubtedly one of the most well-studied problems in Parameterized Complexity. In this problem, given an undirected graph $G$ and a non-negative…

ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs

Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan +2

We present an algorithm for the extensively studied Long Path and Long Cycle problems on unit disk graphs that runs in time $2^{O (k)} (n + m)$ . Under the Exponential Time Hypot…

Structural Parameterizations with Modulator Oblivion

Ashwin Jacob, Fahad Panolan, Venkatesh Raman +1

It is known that problems like Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal are polynomial time solvable in the class of chordal graphs. We consider these problems i…