Counting matrix partitions of graphs

详细信息    查看全文

• 作者：Martin Dyer^a ; Leslie Ann Goldberg^b ; David Richerby^b ; ^{david.richerby@cs.ox.ac.uk" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Matrix partitions of graphs ; Complexity of counting ; Complexity dichotomy ; #P-completeness
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：20 November 2016
• 年：2016
• 卷：213
• 期：Complete
• 页码：76-92
• 全文大小：505 K

文摘

Given a symmetric matrix $M\in {\{0,1,\ast \}}^{D\times D}$, an M$M$-partition of a graph G$G$ is a function from V(G)$V\left(G\right)$ to D$D$ such that no edge of G$G$ is mapped to a 0$0$ of M$M$ and no non-edge to a 1$1$. We give a computer-assisted proof that, when |D|=4$\left|D\right|=4$, the problem of counting the M$M$-partitions of an input graph is either in $\mathrm{FP}$ or is $\mathrm{\#P}$-complete. Tractability is proved by reduction to the related problem of counting list M$M$-partitions; intractability is shown using a gadget construction and interpolation. We use a computer program to determine which of the two cases holds for all but a small number of matrices, which we resolve manually to establish the dichotomy. We conjecture that the dichotomy also holds for |D|>4$\left|D\right|>4$. More specifically, we conjecture that, for any symmetric matrix $M\in {\{0,1,\ast \}}^{D\times D}$, the complexity of counting M$M$-partitions is the same as the related problem of counting list M$M$-partitions.