Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00534
On Polynomial-Time Combinatorial Algorithms for Maximum $L$-Bounded Flow
Vol. 24, no. 3, pp. 303-322, 2020. Regular paper.
Abstract Given a graph $G=(V,E)$ with two distinguished vertices $s,t\in 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.
For networks with unit edge lengths
(or, more generally, with polynomially
bounded edge lengths, with respect to the number of vertices),
the problem can
be solved in polynomial time using linear programming. However, as far as we
know, no polynomial-time combinatorial algorithm1 for the $L$-bounded flow is known.
For general edge lengths, the problem is NP-hard.
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 substantial 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+\varepsilon)$-approximation of the maximum $L$-bounded flow in
time $\mathcal{O}(\varepsilon^{-2}m^2L\log 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.
1Combinatorial in the sense that it does not explicitly use linear programming methods or methods from linear algebra or convex geometry. |
Submitted: August 2019.
Reviewed: March 2020.
Revised: May 2020.
Accepted: May 2020.
Final: June 2020.
Published: June 2020.
Communicated by
Susanne Albers
|
Journal Supporters
|