论文标题
识别图形和曲霉连接功能
Recognising Graphic and Matroidal Connectivity Functions
论文作者
论文摘要
设置$ e $上的a {\ em连接函数}是一个函数$λ：2^e \ rightarrow \ mathbb r $ $所有$ x，y \ subseteq e $的λ（x）+λ（y）$。图形，矩形以及更普遍的多肌膜具有关联的连接函数。在本文中，我们提供了一种识别连接函数何时来自图的方法。该方法使用连接函数的多项式评估数量。相比之下，我们表明，识别何时连接函数来自矩阵的问题无法在多项式时间内解决。我们还表明，识别连通性何时不能在多项式时间内解决连通性函数的问题。
A {\em connectivity function} on a set $E$ is a function $λ:2^E\rightarrow \mathbb R$ such that $λ(\emptyset)=0$, that $λ(X)=λ(E-X)$ for all $X\subseteq E$, and that $λ(X\cap Y)+λ(X\cup Y)\leq λ(X)+λ(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.
