Safety of Flow Decompositions in DAGs

Network flows are one of the most studied combinatorial optimization problems with innumerable applications. Any flow on a directed acyclic graph (DAG) $G$ having $n$ vertices and $m$ edges can be decomposed into a set of $O(m)$ paths, with applications from network routing to assembly of biological sequences. In some applications, the flow decomposition corresponds to some particular data that need to be reconstructed from the flow, which require finding paths (or subpaths) appearing in all possible flow decompositions, referred to as safe paths. Recently, Ma et al. [WABI 2020] addressed a related problem in a probabilistic framework. Later, they gave a quadratic-time algorithm based on a global criterion, for a generalized version (AND-Quant) of the corresponding problem, i.e., reporting if a given flow path is safe. Our contributions are as follows: 1- A simple characterization for the safety of a given path based on a local criterion, which can be directly adapted to give an optimal linear time verification algorithm. 2- A simple enumeration algorithm that reports all maximal safe paths on a flow network in $O(mn)$ time. The algorithm reports all safe paths using a compact representation of the solution (called ${\cal P}_c$), which is $\Omega(mn)$ in the worst case, but merely $O(m+n)$ in the best case. 3- An improved enumeration algorithm where all safe paths ending at every vertex are represented as funnels using $O(n^2+|{\cal P}_c|)$ space. These can be computed and used to report all maximal safe paths, using time linear in the total space required by funnels, with an extra logarithmic factor. Overall we present a simple characterization for the problem leading to an optimal verification algorithm and a simple enumeration algorithm. The enumeration algorithm is improved using the funnel structures for safe paths, which may be of independent interest.