[Colloquium] Kim/Dissertation Defense/Apr 30, 2018

[Margaret Jaffey via Colloquium]

       Department of Computer Science/The University of Chicago

                     *** Dissertation Defense ***


Candidate:  Hong Kyun (David) Kim

Date:  Monday, April 30, 2018

Time:  1:30 PM

Place:  Ryerson 277

Title: Approximation and Hardness of Routing on Disjoint Paths

Abstract:
In the classical Node-Disjoint Paths (\NDP) problem, one is given as
input an $n$-vertex graph $G$ and a collection
$\mset=\set{(s_1,t_1),\ldots,(s_k,t_k)}$ of pairs of vertices of $G$
called \emph{source-destination} or \emph{demand pairs}, and the goal
is to find a maximum-cardinality set of pairwise vertex-disjoint paths
connecting the demand pairs. Despite being one of the most basic
routing problems, there has been a wide gap in our understanding of
the approximability status of \NDP. Currently, the best upper bound of
$O(\sqrt{n})$ is achieved by a simple, greedy algorithm, while until
very recently, the best known hardness of approximation result was an
$\Omega(\log^{1/2-\delta}n)$ lower bound for any constant $\delta$,
under standard complexity assumptions. This gap in the approximability
had been open for special cases of the problem, including when the
input graph $G$ is constrained to be planar, and surprisingly, even
when $G$ is a $\sqrt{n}\times\sqrt{n}$ square grid.

This thesis studies the approximability of \NDP and its special cases.
The first part of the thesis presents approximation algorithms for the
special cases of \NDP when the input graph is constrained to be a
square grid or a general planar graph. We provide approximation
algorithms which improve on the $O(\sqrt{n})$ upper bound on the
approximation factor achieved by a simple, greedy algorithm. The
algorithms presented in this thesis are based on the joint works with
Chuzhoy~\cite{NDP-grids} and Chuzhoy and Li~\cite{NDP-planar}.

The second part of the thesis presents improved inapproximability
results for \NDP, based on joint works with Chuzhoy and
Nimavat~\cite{NDPhardness2017,NDP-hardness-grid}. The first result
shows that \NDP is $2^{\Omega(\sqrt{\log n})}$-hard to approximate,
assuming $\NP\nsubseteq\DTIME(n^{O(\polylog n})$, even when the
underlying graph is a sub-cubic planar graph with all sources $s_i$ of
the demand pairs lying on the boundary of a single face. The second
result shows that \NDP is $2^{\Omega(\log^{1-\epsilon}n)}$-hard to
approximate for any constant $\epsilon$, assuming
$\NP\nsubseteq\RTIME(n^{\poly\log n})$, and that it is
$n^{\Omega(1/(\log\log n)^2)}$-hard to approximate, assuming that
assuming $\NP\nsubseteq\RTIME(2^{n^\delta})$ for some constant
$\delta>0$.

We show that most of the above results hold for the closely related
Edge-Disjoint Paths (\EDP) problem, and the special case of \EDP in
wall graphs, the analogous problem of \NDP in grids for \EDP. %In
fact, all of the above results hold for the \EDP problem, except for
the improved approximation for \NDP in general planar graphs. For \EDP
in planar graphs, the best upper bound on the approximation factor
achieved by an efficient algorithm is still $O(\sqrt{n})$.

Hong Kyun (David)'s advisors are Prof. Laszlo Babai and Prof. Julia Chuzhoy

Login to the Computer Science Department website for details,
including a draft copy of the dissertation:

 https://www.cs.uchicago.edu/phd/phd_announcements#hongk

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margaret P. Jaffey            margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 156)               (773) 702-6011
The University of Chicago      http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=