# Safe Approximation--An Efficient Solution for a Hard Routing Problem
###### Abstract  
The _Disjoint Connecting Paths_ problem and its capacitated generalization, called _Unsplittable Flow_ problem, play an important role in practical applications such as communication network design and routing. These tasks are **NP**-hard in general, but various polynomial-time approximations are known. Nevertheless, the approximations tend to be either too loose (allowing large deviation from the optimum), or too complicated, often rendering them impractical in large, complex networks. Therefore, our goal is to present a solution that provides a relatively simple, efficient algorithm for the unsplittable flow problem in large directed graphs, where the task is **NP**-hard, and is known to remain **NP**-hard even to approximate up to a large factor. The efficiency of our algorithm is achieved by sacrificing a small part of the solution space. This also represents a novel paradigm for approximation. Rather than giving up the search for an _exact_ solution, we restrict the solution space to a subset that is the most important for applications, and excludes only a small part that is marginal in some well-defined sense. Specifically, the sacrificed part only contains scenarios where some edges are very close to saturation. Since nearly saturated links are undesirable in practical applications, therefore, excluding near saturation is quite reasonable from the practical point of view. We refer the solutions that contain no nearly saturated edges as _safe solutions_, and call the approach _safe approximation_. We prove that this safe approximation can be carried out efficiently. That is, once we restrict ourselves to safe solutions, we can find the _exact_ optimum by a randomized polynomial time algorithm. Keywords:routing; **NP**-complete; **NP**-hard; approximation; polynomial time algorithm; disjoint connecting paths; unsplittable flow; network design +
Footnote †: journal:  
0
Footnote 0: _Copyright_: © 2021 by the authors. Licenses MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license ([[https://creativecommons.org/licenses/by/4.0/](https://creativecommons.org/licenses/by/4.0/)]([https://creativecommons.org/licenses/by/4.0/](https://creativecommons.org/licenses/by/4.0/))). that is, the sum of the flows of paths that traverse the edge cannot be more than the capacity of the edge. The name _Unsplittable Flow_ expresses the requirement that between each source-destination pair the flow must follow a single route, it cannot split. Note that the disjointness of the paths themselves is not required _a priori_ in the Unsplittable Flow, but can be enforced by the capacity constraints, if needed. The Unsplittable Flow problem is widely regarded as a fundamental task in communication network design and routing applications. Note that it directly subsumes the Disjoint Connecting Paths problem as a special case, which can be obtained by taking all capacities and flow demands equal to 1. In this paper, after reviewing some existing results, we show that the Unsplittable Flow problem, which is known to be **NP**-hard (and its decision version is **NP**-complete), becomes efficiently solvable if we impose a mild and practically well justifiable restriction. Specifically, our key idea is that we \"cut down\" a small part of the solution space by slightly reducing the edge capacities. In other words, we exclude solutions that are close to saturating some edges, which would be practically undesirable, anyway. We call remaining solutions _safe solutions_: safe in the sense that no link is very close to saturation. Why is this slight capacity reduction useful? Its usefulness is based on the fact, which we constructively prove in the paper, that if we restrict ourselves to safe solutions only, then the hard algorithmic problem becomes solvable by a relatively simple randomized polynomial time algorithm.