Location: MF 14

Speaker: Andres López Martínez (TU/e)

Title: Finding Diverse Minimum s-t Cuts

Abstract: 
Recently, many studies have been devoted to finding diverse solutions in classical combinatorial problems. Finding diverse solutions is important in settings where the user is not able to specify all criteria of the desired solution. We initiate the algorithmic study of k-DIVERSE MINIMUM s-t CUTS which, given a directed graph G=(V,E), two specified vertices s,t∈V, and an integer k>0, asks for a collection of k minimum s-t cuts in G that has maximum diversity. We investigate the complexity of the problem when the diversity of a collection of minimum s-t cuts is measured as the sum of all the pairwise Hamming distances. We show that k-DIVERSE MINIMUM s-t CUTS can be solved in strongly polynomial time for this diversity measure by establishing a connection between ordered collections of minimum s-t cuts, the theory of distributive lattices, and submodular function minimization. The result stands in contrast to the problem of finding k diverse global minimum cuts, which is known to be NP-hard even in the disjoint case. This is joint work with Mark de Berg and Frits Spieksma.