A {em connectivity function} on a set $E$ is a function $lambda:2^Erightarrow mathbb R$ such that $lambda(emptyset)=0$, that $lambda(X)=lambda(E-X)$ for all $Xsubseteq E$, and that $lambda(Xcap Y)+lambda(Xcup Y)leq lambda(X)+lambda(Y)$ for all $X,Y subseteq E$. Graphs, matroids and, more generally, polymatroids have associated connectivity functions. In this paper we give a method for identifying when a connectivity function comes from a graph. This method uses no more than a polynomial number of evaluations of the connectivity function. In contrast, we show that the problem of identifying when a connectivity function comes from a matroid cannot be solved in polynomial time. We also show that the problem of identifying when a connectivity function is not that of a matroid cannot be solved in polynomial time.
Download