A Survey on Covering Supermodular Functions

Summary In this survey we present recent advances on problems that can be described as the construction of graphs or hypergraphs that cover certain set functions with supermodular or related properties. These include a wide range of network design and connectivity augmentation and orientation problems, as well as some results on colourings and matchings. In the first part of the paper we survey results that follow from the totally dual integral (TDI) property of various systems defined by supermodular-type set functions. One of the aims of the survey is to emphasize the importance of relaxing the supermodularity property to include a wider range of set functions. We show how these relaxations lead to a unified understanding of different types of applications. The second part is devoted to results that, according to our current knowledge, cannot be explained using total dual integrality. We would like to demonstrate that an extensive theory independent of total dual integrality has been developed in the last 15 years, centered around various connectivity augmentation problems. Our survey concentrates on the theoretical foundations, and does not include every detail on applications, since the majority of these applications are described in detail in another survey paper by the first author (Frank 2006). The comprehensive book “Combinatorial Optimization: Polyhedra and Efficiency” by Schrijver (2003) is also a rich resource of results related to submodular functions. It should be noted that sub- and supermodularity have several applications in areas not discussed in this paper. In particular, we should mention the book “Submodular Functions and Optimization” by Fujishige (2005) and the book “Discrete Convex Analysis” by Murota (2003). The former explains the foundations of the theory of submodular functions and describes the methods of submodular analysis, while the latter presents a unified framework for nonlinear discrete optimization by extending submodular function theory using ideas from continuous optimization. Our survey focuses on topics not discussed in detail in those books.