Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949966 | Discrete Applied Mathematics | 2016 | 17 Pages |
Abstract
Given a symmetric matrix Mâ{0,1,â}DÃD, 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 Mâ{0,1,â}DÃD, the complexity of counting M-partitions is the same as the related problem of counting list M-partitions.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Martin Dyer, Leslie Ann Goldberg, David Richerby,