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
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!


-- 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: 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 

Joint work with David H.K. Kim and Rachit Nimavat.

More information about the theory-seminar mailing list