Decomposing a submodular function
Take an arbitrary element $e \in \Omega$. If $f(e) = f_{\Omega-e}(e)$ then $e$ is not affected by the rest of the elements so we can choose $X_1 = \{e\}$ and $X_2 = \Omega-\{e\}$. Otherwise let $X$ be an inclusion-wise minimal subset of $\Omega-e$ such that $f(e) &gt; f_X(e)$. Then $X \cup \{e\}$ should be in the same partition. If $X \cup \{e\} = \Omega$ we conclude that there is no desired partition, otherwise we shrink this set into a single element and recurse.