Search Mailing List Archives
[theory-seminar] TCS+ talk: Wednesday, December 12, Julia Chuzhoy, TTIC
Clément Canonne
ccanonne at cs.stanford.edu
Fri Dec 7 06:22:37 PST 2018
Hi everyone,
For the next TCS+ talk*, and last of the Fall season, Julia Chuzhoy will
be speaking about an "Almost Polynomial Hardness of Node-Disjoint Paths
in Grids."
Come next Wednesday (12th) at 10am (actually, come at 9:55 for
breakfast) to see it!
Best,
-- Clément
* for the people in the back: this is an online, interactive talk we can
all watch from Gates while sipping coffee and asking questions to the
speaker.
-------------------------------
Speaker: Julia Chuzhoy (TTIC)
Title: Almost Polynomial Hardness of Node-Disjoint Paths in Grids
Abstract: In the classical Node-Disjoint Paths (NDP) problem, we are
given an n-vertex graph G, and a collection of pairs of its vertices,
called demand pairs. The goal is to route as many of the demand pairs as
possible, where to route a pair we need to select a path connecting it,
so that all selected paths are disjoint in their vertices.
The best current algorithm for NDP achieves an
$O(\sqrt{n})$-approximation, while, until recently, the best negative
result was a roughly $\Omega(\sqrt{\log n})$-hardness of approximation.
Recently, an improved $2^{\Omega(\sqrt{\log n})}$-hardness of
approximation for NDP was shown, even if the underlying graph is a
subgraph of a grid graph, and all source vertices lie on the boundary of
the grid. Unfortunately, this result does not extend to grid graphs.
The approximability of NDP in grids has remained a tantalizing open
question, with the best upper bound of $\tilde{O}(n^{1/4})$, and the
best lower bound of APX-hardness. In this talk we come close to
resolving this question, by showing an almost polynomial hardness of
approximation for NDP in grid graphs.
Our hardness proof performs a reduction from the 3COL(5) problem to NDP,
using a new graph partitioning problem as a proxy. Unlike the more
standard approach of employing Karp reductions to prove hardness of
approximation, our proof is a Cook-type reduction, where, given an
input instance of 3COL(5), we produce a large number of instances of
NDP, and apply an approximation algorithm for NDP to each of them. The
construction of each new instance of NDP crucially depends on the
solutions to the previous instances that were found by the approximation
algorithm.
Joint work with David H.K. Kim and Rachit Nimavat.
More information about the theory-seminar
mailing list