We consider determinantal point processes (DPPs) constrained by spanning trees. Given a graph $G=(V,E)$ and a positive semi-definite matrix $\mathbf{A}$ indexed by $E$, a spanning-tree DPP defines a distribution such that we draw $S\subseteq E$ with probability proportional to $\det(\mathbf{A}_S)$ only if $S$ induces a spanning tree. We prove $\sharp\textsf{P}$-hardness of computing the normalizing constant for spanning-tree DPPs and provide an approximation-preserving reduction from the mixed discriminant, for which FPRAS is not known. We show similar results for DPPs constrained by forests.
翻译:我们考虑的是受横贯树木制约的决定性点过程。 如果用一个图形$G=(V,E) 和正的半限定基质基体$\mathbf{A}美元以美元指数计算, 横贯树木的DPP定义了一种分配方式,只有用美元来诱导横贯树木的树,我们才能以美元来比照(\mathbf{A ⁇ S) 的概率来提取$S\subseteq E$。 我们证明, 美元是计算横贯树木的 DPPs 正常化常数的硬性, 并且提供了混合的色彩的近似保存减值, 而FPRAS并不知道这一点。 我们对受森林制约的DPPs 显示类似的结果 。