Shortest Cycles With Monotone Submodular Costs

Abstract

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 $\text{OPT}=f(C)$. We give an algorithm that given an $n$-vertex graph $G$, parameter $\epsilon >0$, and the function $f$ represented by an oracle, in time $n^{\mathcal{O}(\log 1/\epsilon )}$ finds a cycle $C$ in $G$ with $f(C)\le (1+\epsilon )\cdot \text{OPT}$. 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-\epsilon }$-approximation [Goel et al., FOCS 2009]. We complement our algorithm with a matching lower bound. We show that for every $\epsilon >0$, obtaining a $(1+\epsilon )$-approximation requires at least $n^{\Omega (\log 1/\epsilon )}$ queries to the oracle. When the function $f$ is integer-valued, our algorithm yields that a cycle of cost $\text{OPT}$ can be found in time $n^{\mathcal{O}(\log \text{OPT})}$. In particular, for $\text{OPT}=n^{\mathcal{O}(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^{\mathcal{O}(\log n)}$ queries are required even when $\text{OPT}=\mathcal{O}(n)$.

17 pages, 1 figure. Accepted to SODA 2023