Let $S$ be a finite set. Following Lovasz (Matroid matching and some applications), 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.

  • 3
    $\begingroup$ Matroid intersection captures bipartite matching. Counting bipartite matchings is #P hard, isn't it? $\endgroup$ – Chandra Chekuri Mar 25 '14 at 13:41
  • 1
    $\begingroup$ 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? $\endgroup$ – NisaiVloot Mar 25 '14 at 13:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.