My research is in Theoretical Computer Science, with a primary focus on the design and analysis of Approximation Algorithms for fundamental graph problems and understanding their limits through Hardness of Approximation. So far, I have worked on problems that arise in the context of Graph Routing and Graph Minors.
Publications & Preprints
Large Minors in Expanders.
Julia Chuzhoy and Rachit Nimavat.
A graph $H$ is a minor of $G$, if $H$ can be obtained from $G$ via a sequence of vertex and edge-deletions and edge-contractions.
We show that given any bounded-degree expander $G$ on $n$ vertices and an arbitrary graph $H$ on roughly $n/\log n$ vertices, $H$ is a minor of $G$.
We also show a randomized algorithm to find such a model of $H$ in $G$.
Independently, Krivelevich and Nenadov provide an elegant proof of a similar but stronger result.
Improved Approximation for Node-Disjoint Paths in Grids with Sources on the Boundary.
Julia Chuzhoy, David Kim and Rachit Nimavat.
Node-Disjoint Paths ($\operatorname{NDP}$) is a problem where we are given a graph and some source-destination pairs. The goal is to ‘route’ as many of these pairs of vertices as possible, along paths that don’t intersect anywhere. We give an approximation algorithm for a special case of $\operatorname{NDP}$ problem: (i) the graph is an undirected grid; and (ii) the sources lie on its boundary.
Almost Polynomial Hardness for Node-Disjoint Paths in Grids.
Julia Chuzhoy, David Kim and Rachit Nimavat.
STOC 2018. Gave a talk about this result at Workshop on Approximation algorithms and Hardness of Approximation, Banff, CA, Nov, 2017. [arxiv] [slides] [video]
Node-Disjoint Paths ($\operatorname{NDP}$) is a problem where we are given a graph and some source-destination pairs. The goal is to ‘route’ as many of these pairs of vertices as possible, along paths that don’t intersect anywhere. We show that it is hard to approximate the solution, even when the graph is a grid. The hardness of approximation factor that we achieve is almost polynomial.
New Hardness Results for Routing on Disjoint Paths.
Julia Chuzhoy, David Kim and Rachit Nimavat.
Node-Disjoint Paths ($\operatorname{NDP}$) is a problem where we are given a graph and some source-destination pairs. The goal is to ‘route’ as many of these pairs of vertices as possible, along paths that don’t intersect anywhere. We show that it is hard to approximate the solution, even when the graph is a grid. The hardness of approximation factor that we achieve is almost polynomial.