Counting 4 4 matrix partitions of graphs

DOI10.1016/J.DAM.2016.05.001zbMATH Open1344.05113arXiv1407.7799OpenAlexW1480571425WikidataQ56323759 ScholiaQ56323759MaRDI QIDQ313799FDOQ313799

Authors: Martin Dyer, Leslie Ann Goldberg, David Richerby 

Publication date: 12 September 2016

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

Abstract: Given a symmetric matrix $Min{0,1,*}^{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,*}^{DimesD}$, the complexity of counting $M$-partitions is the same as the related problem of counting list $M$-partitions.

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

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

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)

Cites Work

• Title not available (Why is that?)
• 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
• Complexity of graph partition problems
• List Partitions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Counting partitions of graphs

Cited In (7)

• Title not available (Why is that?)
• Counting List Matrix Partitions of Graphs
• Partitions of multigraphs without \(C_4\)
• Counting minimal reactions with specific conditions in \(\mathbb R^4\)
• Lower bound for the number of 4-element generating sets of direct products of two neighboring partition lattices
• Counting \(K_4\)-subdivisions
• Counting partitions of graphs

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)