Connectivity of submodular functions (Q1199483)

This paper relates the connectivity of submodular functions \(f\) to that of certain submodular functions which are derived from \(f\). Here the function \(f\) on \(S\) is submodular if \(f(A)+f(B)\geq f(A\cup B)+f(A\cap B)\) for all subsets \(A\) and \(B\) of \(S\). The connectivity function \(c_ f\) of the submodular function \(f\) on \(S\) is defined by \(c_ f(A)=f(A)+f(S-A)- f(S)-f(0)\) for all subsets \(A\) of \(S\). The authors defined \(\overline c_ f\) to be minimum value that \(c_ f\) takes on nonempty proper subsets of \(S\) unless \(| S|\leq 1\). One of the two main results of this paper generalizes Tutte's result to submodular functions. This shows that if for a subset \(A\) of the ground set \(S\) we have \(c_ f(A)<2\overline c_ f\) then at least one of the operations of delection of \(A\) from \(f\) and of contraction of \(A\) from \(f\) is connected. In the second section of this paper is introduced and investigated a new operation on submodular functions which does correspond to contraction in graphs.