Finding multiple induced disjoint paths in general graphs
In an undirected graph, paths P(1), P(2),.... P(k) are induced disjoint if each one of them is chordless (i.e., is an induced path) and any two of them have neither common nodes nor adjacent nodes. This paper investigates the Maximum Induced Disjoint Paths (MIDP) problem: in an undirected graph G = (V, E), given k node pairs {s(1), t(1)} ... {s(k), t(k)}, connect maximum number of these node pairs via induced disjoint paths. Till now, the only things known about MIDP are: i) it is NP-hard; ii) it is NP-hard even when k = 2; iii) it can be solved in polynomial time when k is a fixed constant and the given graph is a directed planar graph (Kobayashi. 2009 [9]). This paper proves that for general k and any epsilon > 0, it is NP-hard to approximate MIDP within m(1/2-epsilon), where m = vertical bar E vertical bar. Two algorithms for MIDP are given by this paper: a greedy algorithm whose approximation ratio is,root m and an on-line algorithm which has a good lower bound. (C) 2011 Elsevier B.V. All rights reserved.
induced disjoint paths graph approximation algorithm