# Safe Approximation--An Efficient Solution for a Hard Routing Problem
## 2 Previous Results  
Considerable work was done on the Disjoint Connecting Paths problem, since its first appearance as an **NP**-complete task in the classic paper of [PERSON] [1] in 1972. One direction of research deals with finding the \"heart\" of the difficulty--the simplest restricted cases that still remain **NP**-complete. (Or **NP**-hard if the optimization version is considered, where we look for the maximum number of connecting paths, allowing that possibly not all source-destination pairs will be connected). [PERSON] and [PERSON] [2] proves, motivated by VLSI layout design, that the problem remains **NP**-complete even for graphs as regular as a two dimensional mesh. If we restrict ourselves to undirected planar graphs with each vertex having degree at most three, the problem also remains **NP**-complete, as proven by [PERSON] and [PERSON] [3]. The optimization version remains **NP**-hard for trees with parallel edges, although there the decision problem is already solvable in polynomial time [4]. The restriction that we only allow paths which connect each source node with a _dedicated_ target is essential. If this is relaxed and we are satisfied with edge disjoint paths that connect each source \(s_{i}\) with _some_ of destinations \(t_{j}\) but not necessarily with \(t_{i}\), then the problem becomes solvable with classical network flow techniques. Thus, the prescribed matching of sources and destinations causes a dramatic change in the problem complexity. Interestingly, it becomes already **NP**-complete if we require that just _one_ of the sources is connected to a dedicated destination, the rest is relaxed as above ([PERSON] [5]). Another group of results produces polynomial time algorithmic solutions for finding the paths, possibly using randomization, in _special classes_ of graphs. For example, [PERSON] and [PERSON] [3] proves the following. Let us represent the terminator pairs by _demand edges_. These are additional edges that connect a source with its destination. If this extended graph is embeddable in the plane such that the demand edges lie in a bounded number of faces of the original graph, then the problem is solvable in polynomial time. (The faces are the planar regions bordered by the curves that represent the edges in the planar embedding, that is, in drawing the graph in the plane). Thus, this special case requires that, beyond the planarity of the extended graph, the terminators are concentrated in a constant number of regions (independent of the graph size), rather than spreading over the graph. [PERSON], [PERSON], [PERSON] and [PERSON] [6] consider the case of _random graphs_ and provide a randomized algorithm that, under some technical conditions, finds a solution with high probability in time \(O(\text{nm}^{2})\) for a random graph of \(n\) vertices and \(m\) edges. A deep theoretical result, due to [PERSON] and [PERSON] [7], is that for general undirected graphs the problem can be solved in polynomial time if the number \(k\) of paths to be found is _constant_ (i.e., cannot grow with the size of the graph). This is important from the theoretical point of view, but does not lead to a practical algorithm, as analyzed by [PERSON] and [PERSON] [8]. On the other hand, for directed graphs the problem becomes **NP**-complete already for the smallest nontrivial case of \(k=2\), as proven by [PERSON], [PERSON], and [PERSON] [9]. Another line of research aims at finding approximations to the optimization version. An algorithm is said to be an \(f(n)\)-approximation if it can connect a subset of the terminator pairs by disjoint paths such that this subset is at most \(f(n)\) times smaller than the optimum in a graph of \(n\) vertices. For example, in this terminology a 2-approximation algorithm always reaches at least the half of the optimum, or an \(O(\log n)\)-approximation reaches at least a \(c/\log n\) fraction of the optimum, for \(n>n_{0}\) with some constants \(c,n_{0}\). Various approximations have been presented in the literature.