2019/11/15 by Graur, Andrei, Pollner, Tristan, Ramaswamy, Vidhya +1 · 5 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1911.06889
We consider submodular function minimization in the oracle model: given black-box access to a submodular set function f:2[n]→ ℝ, find an element of argminS \f(S)\ using as few queries to f(⋅) as possible. State-of-the-art algorithms succeed with O(n2) queries [LeeSW15], yet the best-known lower bound has never been improved beyond n [Harvey08]. We provide a query lower bound of 2n for submodular function minimization, a 3n/2-2 query lower bound for the non-trivial minimizer of a symmetric submodular function, and a \binomn2 query lower bound for the non-trivial minimizer of an asymmetric submodular function. Our 3n/2-2 lower bound results from a connection between SFM lower bounds and a novel concept we term the cut dimension of a graph. Interestingly, this yields a 3n/2-2 cut-query lower bound for finding the global mincut in an undirected, weighted graph, but we also prove it cannot yield a lower bound better than n+1 for s-t mincut, even in a directed, weighted graph.