Exponential Space Complexity for Symbolic Maximum Flow Algorithms in 0-1 Networks

摘要

The maximum flow problem is a central problem in graph algorithms and optimization and OBDDs are one of the most common dynamic data structures for Boolean functions. Since in some applications graphs become larger and larger, a research branch has emerged which is concerned with the theoretical design and analysis of symbolic algorithms for classical graph problems on OBDD-represented graph instances. The algorithm for the maximum flow problem in 0-1 networks by Hachtel and Somenzi (1997) has been one of the first of these symbolic algorithms. Typically problems get harder when their input is represented symbolically, nevertheless not many concrete non-trivial lower bounds are known. Here, answering an open question posed by Sawitzki (2006) the first exponential lower bound on the space complexity of OBDD-based algorithms for the maximum flow problem in 0-1 networks is presented.