## Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through

# [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.