<p>Let $S$ be a finite set. Following Lovasz (<a href="http://ac.els-cdn.com/0095895680900660/1-s2.0-0095895680900660-main.pdf?_tid=f0b3e4cc-b41a-11e3-b981-00000aacb35f&amp;acdnat=1395751535_bc97d640dee3077a7a8f7a14bc6c6f90" rel="nofollow">Matroid matching and some applications</a>), let us define a <em>polymatroid function over $S$</em> as a function $f : 2^S \rightarrow \mathbb{N}$ such that</p>

<p>(1) $f(\emptyset) = 0$,</p>

<p>(2) $X \subseteq Y \Rightarrow f(X) \leq f(Y)$,</p>

<p>(3) $f(X \cup Y) + f(X \cap Y) \leq f(X) + f(Y)$.</p>

<p>The function $f$ defines a <em>2-polymatroid</em> if $f({x}) \leq 2$ for every $x \in S$. My question is as follows: given two such functions $f,g$ over the same set $S$, and given two integers $r,s$, what is the complexity of counting sets $Z \subseteq S$ such that $f(Z) = r$ and $g(Z) = s$?</p>

<p>The $\# \mathsf{P}$-hardness of this problem is not clear to me, if by chance it was in $\mathsf{P}$ it would have some interesting consequences. Indeed, it encompasses natural problems such as counting the number of $k$-vertex trees in a graph, which complexity is open afaik.</p>

CC BY-SA 3.0
2014-03-25T13:41:49.317Z
Matroid intersection captures bipartite matching. Counting bipartite matchings is #P hard, isn't it?
Chandra Chekuri
CC BY-SA 3.0
2014-03-25T13:52:27.290Z
I had the same idea but it was not clear to me whether matroid intersection can be expressed in this framework. The question is: given a matroid $M$, is it true that the function $f_M(X)=|X|−r_M(X)$ defines a 2-polymatroid?
NisaiVloot
<counting-complexity>
Counting problems with two-polymatroids
NisaiVloot
# Counting problems with two-polymatroids

(Asked by: username_0 on 2014-03-25)

Let $S$ be a finite set. Following Lovasz ([Matroid matching and some applications](http://ac.els-cdn.com/0095895680900660/1-s2.0-0095895680900660-main.pdf?_tid=f0b3e4cc-b41a-11e3-b981-00000aacb35f&acdnat=1395751535_bc97d640dee3077a7a8f7a14bc6c6f90)), let us define a *polymatroid function over $S$* as a function $f : 2^S \rightarrow \mathbb{N}$ such that

(1) $f(\emptyset) = 0$,

(2) $X \subseteq Y \Rightarrow f(X) \leq f(Y)$,

(3) $f(X \cup Y) + f(X \cap Y) \leq f(X) + f(Y)$.

The function $f$ defines a *2-polymatroid* if $f({x}) \leq 2$ for every $x \in S$. My question is as follows: given two such functions $f,g$ over the same set $S$, and given two integers $r,s$, what is the complexity of counting sets $Z \subseteq S$ such that $f(Z) = r$ and $g(Z) = s$?

The $\# \mathsf{P}$-hardness of this problem is not clear to me, if by chance it was in $\mathsf{P}$ it would have some interesting consequences. Indeed, it encompasses natural problems such as counting the number of $k$-vertex trees in a graph, which complexity is open afaik.

**Tags:** counting-complexity
> **Comments:**
> **username_1**: Matroid intersection captures bipartite matching. Counting bipartite matchings is #P hard, isn't it?  
> **username_0**: I had the same idea but it was not clear to me whether matroid intersection can be expressed in this framework. The question is: given a matroid $M$, is it true that the function $f_M(X)=|X|−r_M(X)$ defines a 2-polymatroid?  

---

## 0 answers

