A fast parametric submodular intersection algorithm for strong map sequences

This paper presents a fast algorithm to solve the intersection problem for a pair of nondecreasing and nonincreasing strong map sequences of submodular systems. The worst-case time bound is the same as that of the push/relabel algorithm for a single intersection problem. This extends the Gallo–Grigoriadis–Tajan (GGT) method for parametric maximum flow problems and reveals an algorithmic significance of the concept of strong maps for submodular systems.