# 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.

• Do you mean to say that $f(S) = f_1(S \cap X_1) + f_2(S \cap X_2)$ where $f_1$ and $f_2$ are submodular on $X_1$ and $X_2$ respectively? – Chandra Chekuri Nov 15 '11 at 4:56
• Yes, I indeed meant that. Thanks for pointing the typo, I will correct it. – Ashwinkumar B V Nov 15 '11 at 5:23
• I am not sure whether what I say below is correct but here is the idea. 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) > f_X(e)$. Then it would seem that $X \cup \{e\}$ should be in the same partition and hence we can shrink the set into a single element and recurse if it is stricly smaller than $\Omega$, otherwise we conclude that no desired partition exists. – Chandra Chekuri Nov 15 '11 at 16:03
• Decided to make the comment into an answer. – Chandra Chekuri Nov 18 '11 at 3:14

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) > 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.