Recognising Graphic and Matroidal Connectivity Functions

Abstract

A {\em connectivity function} on a set $E$ is a function $\lambda :2^E\to \mathbb{R}$ such that $\lambda (\varnothing )=0$, that $\lambda (X)=\lambda (E-X)$ for all $X\subseteq E$, and that $\lambda (X\cap Y)+\lambda (X\cup Y)\le \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.