Shortest Cycles With Monotone Submodular Costs
share
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 =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^𝒪(log 1/ε) finds a cycle C in G with f(C)≤ (1+ε)·. 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 can be found in time n^𝒪(log). In particular, for =n^𝒪(1) this gives a quasipolynomial-time algorithm computing a cycle of minimum submodular cost. Interestingly, while a quasipolynomial-time algorithm often serves as a good indication that a polynomial time complexity could be achieved, we show a lower bound that n^𝒪(log n) queries are required even when = 𝒪(n).
READ FULL TEXT