A Note on the Inapproximability of Induced Disjoint Paths

2017/03/13 by Gaoxiu Dong, Weidong Chen, Dong, Gaoxiu +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1703.04300

openalex publication_date 2017/03/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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-ε for a general k and any ε>0. In this paper, we prove that the problem is NP-hard to approximate within n^1-ε for a general k and any ε>0 by giving a simple reduction from the independent set problem.

Related

• Few Induced Disjoint Paths for H-Free Graphs
• Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs
• Constant Approximating Disjoint Paths on Acyclic Digraphs is W[1]-hard
• On Structural Parameterizations of the Edge Disjoint Paths Problem
• Induced Disjoint Paths in Claw-Free Graphs