Decomposing a submodular function Given a submodular function $f$ on $\Omega=X_1\cup X_2$ where $X_1$ and $X_2$ are disjoint and $f(S)=f_1(S\cap X_1)+f_2(S\cap X_2)$. Here $f_1$ and $f_2$ are submodular on $X_1$ and $X_2$ respectively.

Here $X_1,X_2,f_1,f_2$ are unknown and only a value query access to $f$ is given. Then is there a polytime algorithm which finds $X_1$. If there are multiple choices for $X_1$ any of them should be fine.

Some thoughts. If we can find any two elements $t_1,t_2$ such that both either belong to $X_1$ or belong to $X_2$ then we can merge them and proceed recursively. But it is not clear how to implement such a step.
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.