Counting 4 4 matrix partitions of graphs

DOI10.1016/J.DAM.2016.05.001zbMATHOpenAlexWikidataMaRDI QIDQ313799FDO

Authors Martin Dyer, Leslie Ann Goldberg, David Richerby

Publication date 12 September 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1407.7799

zbMATH Keywords

complexity dichotomy\(\#\mathrm{P}\)-completenesscomplexity of countingmatrix partitions of graphs

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Given a symmetric matrix $Min{0,1,\ast }^{DimesD}$, an $M$-partition of a graph $G$ is a function from $V(G)$ to $D$ such that no edge of $G$ is mapped to a $0$ of $M$ and no non-edge to a $1$. We give a computer-assisted proof that, when $|D|=4$, the problem of counting the $M$-partitions of an input graph is either in FP or is #P-complete. Tractability is proved by reduction to the related problem of counting list $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$. More specifically, we conjecture that, for any symmetric matrix $Min{0,1,\ast }^{DimesD}$, the complexity of counting $M$-partitions is the same as the related problem of counting list $M$-partitions.

Recommendations

• Counting List Matrix Partitions of Graphs
• Counting partitions of graphs
• Graph homomorphisms with complex values: a dichotomy theorem
• A Complexity Dichotomy for Partition Functions with Mixed Signs
• Matrix partitions with finitely many obstructions

Cites work

• scientific article; zbMATH DE number 1545676 (Why is no real title available?)
• scientific article; zbMATH DE number 2151253 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• Complexity of graph partition problems
• Counting partitions of graphs
• List Partitions
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The Complexity of Enumeration and Reliability Problems
• The complexity of the counting constraint satisfaction problem
• Towards a dichotomy theorem for the counting constraint satisfaction problem

Cited in

(7)

• Counting \(K_4\)-subdivisions
• Partitions of multigraphs without \(C_4\)
• Lower bound for the number of 4-element generating sets of direct products of two neighboring partition lattices
• Counting minimal reactions with specific conditions in \(\mathbb R^4\)
• Counting partitions of graphs
• Counting List Matrix Partitions of Graphs
• scientific article; zbMATH DE number 5656434 (Why is no real title available?)

This page was built for publication: Counting \(4 \times 4\) matrix partitions of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q313799)