2026-07-22T13:10:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11749 2024-03-06T10:48:37Z ddc:004 open_access

New Query Lower Bounds for Submodular Function Minimization Graur, Andrei Pollner, Tristan Ramaswamy, Vidhya Weinberg, S. Matthew submodular functions query lower bounds min cut 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 arg min_S {f(S)} using as few queries to f(⋅) as possible. State-of-the-art algorithms succeed with Õ(n²) queries [Yin Tat Lee et al., 2015], yet the best-known lower bound has never been improved beyond n [Nicholas J. A. Harvey, 2008]. 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 binom{n}{2} 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andrei Graur and Tristan Pollner and Vidhya Ramaswamy and S. Matthew Weinberg 2020 Is Part Of LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2020.64 urn:nbn:de:0030-drops-117493 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.64 eng https://creativecommons.org/licenses/by/3.0/legalcode