The problem I have is as follows: I know the minimizer/minimum of a non-negative submodular function, and want to use this to efficiently compute the minimizer/minimum of a "perturbed" submodular function.

E.g. Consider the special case of the submodular function being the cut-capacity function; i.e. We have a directed s-t graph $(V,E)$ with $n$ nodes and $m$ edges and the cut-capacity function is defined as $f(S)=\sum_{s\in S,t\in S^c} c(u,v)$ where $S\subseteq V$ and $c(u,v)$ denotes the capacity of the edge $(u,v)$. We find the s-t min-cut $A\subset V$. Now we add/delete an edge to the graph, which changes the cut-capacity function only slightly (i.e. the function value is unchanged for most of the arguments). Finding the new min-cut by utilizing the "warm start" $A$ can be done in time $O(m)$. This is more efficient than finding the min-cut from scratch which takes time at least $O(nm)$.

I am looking for any references/keywords for cases more general than the simple cut-function described above. It doesn't have to be the most general submodular function e.g. I can restrict my attention to graphs but allow the cut function $f:2^V\rightarrow \mathbb{R}_+$ to be a more general (non-negative submodular) function, based on the capacities of the edges crossing the cut.


P.S. I am aware that there is some work on parametric submodular function minimization, however I can't use that since I have to do the above problem repeatedly. E.g. in the graph example I described, I have to add/delete an edge, reoptimize, add/delete an edge, reoptimize and so on. This does not fall in the parametric framework.

  • 2
    $\begingroup$ To me it's not clear what kind of submodular functions you have in mind. Cut functions are natural, but I wonder what is your function that is "more general" than cut functions but still lives around graphs. Do you have a specific example? $\endgroup$ – Yoshio Okamoto Jun 4 '13 at 8:04
  • $\begingroup$ Sure, a very specific example would be this: Consider a a graph with 4 nodes $\{s,r_1,r_2,t\}$. There are 4 edges in this graph $(s,r_1),(s,r_2),(r_1,t),(r_2,t)$ with some positive numbers associated with each edge $c_{sr_1},c_{sr_2},c_{r_1t},c_{r_2t}$ respectively. There are 4 s-t cuts in this graph depending on whether $r_1$ and $r_2$ are included in the cut or not. The cut function can be: $f(\{s\}) = \log(1+c_{sr_1}+c_{sr_2})$, $f(\{s,r_1\}) = \log(1+c_{sr_2})+\log(1+c_{r_1t})$, $f(\{s,r_2\}) = \log(1+c_{sr_1})+\log(1+c_{r_2t})$, $f(\{s,r_1,r_2\}) = \log(1+c_{r_1t}+c_{r_2t}).$ $\endgroup$ – rk2 Jun 4 '13 at 17:00
  • $\begingroup$ Thank you. Although I don't have an answer, it'd be helpful to other people if you'd include the definition of your class of functions in the question. $\endgroup$ – Yoshio Okamoto Jun 6 '13 at 22:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.