Stackelberg Bipartite Vertex Cover and the Preflow Algorithm

Abstract

Stackelberg pricing of vertex covers in a bipartite graph, with the priceable nodes on one side of the bipartition, reduces to a sequence of maximum flow problems. This was shown by Briest et al. (Algorithmica 62:733–753, 2012), leading to an (Formula presented.) algorithm. Here (Formula presented.) is the number of nodes of the graph. We show how the use of the preflow algorithm gives an (Formula presented.) algorithm.