Source author record

David H. K. Kim

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms

Catalog footprint

Research overview

2works

1topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Improved Approximation for Node-Disjoint Paths in Planar Graphs

We study the classical Node-Disjoint Paths (NDP) problem: given an $n$ -vertex graph $G$ and a collection $M=\{(s_1,t_1),\ldots,(s_k,t_k)\}$ of pairs of vertices of $G$ called demand pairs, find a maximum-cardinality set of node-disjoint paths connecting the demand pairs. NDP is one of the most basic routing problems, that has been studied extensively. Despite this, there are still wide gaps in our understanding of its approximability: the best currently known upper bound of $O(\sqrt n)$ on its approximation ratio is achieved via a simple greedy algorithm, while the best current negative result shows that the problem does not have a better than $Ω(\log^{1/2-δ}n)$ -approximation for any constant $δ$ , under standard complexity assumptions. Even for planar graphs no better approximation algorithms are known, and to the best of our knowledge, the best negative bound is APX-hardness. Perhaps the biggest obstacle to obtaining better approximation algorithms for NDP is that most currently known approximation algorithms for this type of problems rely on the standard multicommodity flow relaxation, whose integrality gap is $Ω(\sqrt n)$ for NDP, even in planar graphs. In this paper, we break the barrier of $O(\sqrt n)$ on the approximability of the NDP problem in planar graphs and obtain an $\tilde O(n^{9/19})$ -approximation. We introduce a new linear programming relaxation of the problem, and a number of new techniques, that we hope will be helpful in designing more powerful algorithms for this and related problems.

preprint2016arXiv

New Hardness Results for Routing on Disjoint Paths

In the classical Node-Disjoint Paths (NDP) problem, the input consists of an undirected $n$ -vertex graph $G$ , and a collection $\mathcal{M}=\{(s_1,t_1),\ldots,(s_k,t_k)\}$ of pairs of its vertices, called source-destination, or demand, pairs. The goal is to route the largest possible number of the demand pairs via node-disjoint paths. The best current approximation for the problem is achieved by a simple greedy algorithm, whose approximation factor is $O(\sqrt n)$ , while the best current negative result is an $Ω(\log^{1/2-δ}n)$ -hardness of approximation for any constant $δ$ , under standard complexity assumptions. Even seemingly simple special cases of the problem are still poorly understood: when the input graph is a grid, the best current algorithm achieves an $\tilde O(n^{1/4})$ -approximation, and when it is a general planar graph, the best current approximation ratio of an efficient algorithm is $\tilde O(n^{9/19})$ . The best currently known lower bound on the approximability of both these versions of the problem is APX-hardness. In this paper we prove that NDP is $2^{Ω(\sqrt{\log n})}$ -hard to approximate, unless all problems in NP have algorithms with running time $n^{O(\log n)}$ . Our result holds even when the underlying graph is a planar graph with maximum vertex degree $3$ , and all source vertices lie on the boundary of a single face (but the destination vertices may lie anywhere in the graph). We extend this result to the closely related Edge-Disjoint Paths problem, showing the same hardness of approximation ratio even for sub-cubic planar graphs with all sources lying on the boundary of a single face.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.