Shortest Cycles With Monotone Submodular Costs

We introduce the following submodular generalization of the Shortest Cycle problem. For a nonnegative monotone submodular cost function f defined on the edges (or the vertices) of an undirected graph G, we seek for a cycle C in G of minimum cost OPT = f (C). We give an algorithm that given an n-vertex graph G, parameter ε > 0, and the function f represented by an oracle, in time n

This is in sharp contrast with the non-approximability of the closely related Monotone Submodular Shortest (s, t)-Path problem, which requires exponentially many queries to the oracle for finding an n 2/3-ε -approximation [Goel et al., FOCS 2009]. We complement our algorithm with a matching lower bound. We show that for every ε > 0, obtaining a (1 + ε)-approximation requires at least n Ω(log 1/ε) queries to the oracle.

When the function f is integer-valued, our algorithm yields that a cycle of cost OPT can be found in time n O(log OPT) . In particular, for OPT = n O(1) this gives a quasipolynomial-time algorithm computing a cycle of minimum submodular cost. Interestingly, while a quasipolynomialtime algorithm often serves as a good indication that a polynomial time complexity could be achieved, we show a lower bound that n O(log n) queries are required even when OPT = O(n).