A Note on the Inapproximability of Induced Disjoint Paths
pith:CZNZ7J55 Add to your LaTeX paper
What is a Pith Number?\usepackage{pith}
\pithnumber{CZNZ7J55}
Prints a linked pith:CZNZ7J55 badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more
read the original 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^{{1\over 2}-\varepsilon}$ for a general $k$ and any $\varepsilon>0$. In this paper, we prove that the problem is NP-hard to approximate within $n^{1-\varepsilon}$ for a general $k$ and any $\varepsilon>0$ by giving a simple reduction from the independent set problem.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.