A Note on the Inapproximability of Induced Disjoint Paths

Abstract

We study the inapproximability of the induced disjoint paths problem on an arbitrary $n$-node $m$-edge undirected graph, which is to connect the maximum number of the $k$ source-sink pairs given in the graph via induced disjoint paths. It is known that the problem is NP-hard to approximate within $m^{\frac{1}{2}-\epsilon }$ for a general $k$ and any $\epsilon >0$. In this paper, we prove that the problem is NP-hard to approximate within $n^{1-\epsilon }$ for a general $k$ and any $\epsilon >0$ by giving a simple reduction from the independent set problem.

4 pages