VLDB 2026 Research / reviewers in the wild / expert
Vraj Patel 0001
dblp:264/5695-1
· DBLP profile ↗
3ranked-venue papers
0as first author
1since 2021 · last 2024
0009-0005-1722-868XORCID · corroborated
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 3 · 1 since 2021
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2024 | Improved FPT Algorithms for Deletion to Forest-Like Structures
Kishen N. Gowda, Aditya Lonkar, Fahad Panolan, Vraj Patel 0001, Saket Saurabh 0001 |
Algorithmica | 4 |
| 2020 | Improved FPT Algorithms for Deletion to Forest-Like StructuresabstractThe 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 integer $k$, the objective is to test whether there exists a subset $S\subseteq V(G)$ of size at most $k$ such that $G-S$ is a forest. After a long line of improvement, recently, Li and Nederlof [SODA, 2020] designed a randomized algorithm for the problem running in time $\mathcal{O}^{\star}(2.7^k)$. In the Parameterized Complexity literature, several problems around Feedback Vertex Set have been studied. Some of these include Independent Feedback Vertex Set (where the set $S$ should be an independent set in $G$), Almost Forest Deletion and Pseudoforest Deletion. In Pseudoforest Deletion, each connected component in $G-S$ has at most one cycle in it. However, in Almost Forest Deletion, the input is a graph $G$ and non-negative integers $k,\ell \in \mathbb{N}$, and the objective is to test whether there exists a vertex subset $S$ of size at most $k$, such that $G-S$ is $\ell$ edges away from a forest. In this paper, using the methodology of Li and Nederlof [SODA, 2020], we obtain the current fastest algorithms for all these problems. In particular we obtain following randomized algorithms. 1) Independent Feedback Vertex Set can be solved in time $\mathcal{O}^{\star}(2.7^k)$. 2) Pseudo Forest Deletion can be solved in time $\mathcal{O}^{\star}(2.85^k)$. 3) Almost Forest Deletion can be solved in $\mathcal{O}^{\star}(\min\{2.85^k \cdot 8.54^\ell,2.7^k \cdot 36.61^\ell,3^k \cdot 1.78^\ell\})$. Kishen N. Gowda, Aditya Lonkar, Fahad Panolan, Vraj Patel 0001, Saket Saurabh 0001 |
ISAAC | 4 |
| 2020 | A Parameterized Perspective on Attacking and Defending Elections
Kishen N. Gowda, Neeldhara Misra, Vraj Patel 0001 |
IWOCA | 3 |