<p>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.</p>

CC BY-SA 3.0
2011-11-18T03:14:10.957Z
2011-11-18T03:14:10.957Z
Chandra Chekuri
<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2011-11-15T04:56:14.900Z
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
CC BY-SA 3.0
2011-11-15T05:23:20.743Z
Yes, I indeed meant that. Thanks for pointing the typo, I will correct it.
Ashwinkumar B V
CC BY-SA 3.0
2011-11-15T16:03:49.240Z
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
CC BY-SA 3.0
2011-11-18T03:14:27.350Z
Decided to make the comment into an answer.
Chandra Chekuri
<ds.algorithms><submodularity>
Decomposing a submodular function
Ashwinkumar B V
# Decomposing a submodular function

(Asked by: username_0 on 2011-11-12)

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.

**Tags:** ds.algorithms, submodularity

> **Comments:**
> **username_1**: 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?  
> **username_0**: Yes, I indeed meant that. Thanks for pointing the typo, I will correct it.  
> **username_1**: 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.  
> **username_1**: Decided to make the comment into an answer.  

---

## 1 answers

### Answer by username_1 on 2011-11-18. Score: 5 | Accepted answer

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.


---

