On Polynomial-Time Combinatorial Algorithms for Maximum L-Bounded Flow
share
Given a graph G=(V,E) with two distinguished vertices s,t∈ V and an integer L, an L-bounded flow is a flow between s and t that can be decomposed into paths of length at most L. In the maximum L-bounded flow problem the task is to find a maximum L-bounded flow between a given pair of vertices in the input graph. The problem can be solved in polynomial time using linear programming. However, as far as we know, no polynomial-time combinatorial algorithm for the L-bounded flow is known. The only attempt, that we are aware of, to describe a combinatorial algorithm for the maximum L-bounded flow problem was done by Koubek and Ří ha in 1981. Unfortunately, their paper contains substantional flaws and the algorithm does not work; in the first part of this paper, we describe these problems. In the second part of this paper we describe a combinatorial algorithm based on the exponential length method that finds a (1+ϵ)-approximation of the maximum L-bounded flow in time O(ϵ^-2m^2 L L) where m is the number of edges in the graph. Moreover, we show that this approach works even for the NP-hard generalization of the maximum L-bounded flow problem in which each edge has a length.
READ FULL TEXT