You have just completed your registration at OpenAire.
Before you can login to the site, you will need to activate your account.
An e-mail will be sent to you with the proper instructions.
Important!
Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version
of the site upon release.
Given a symmetric matrix $M\in \{0,1,*\}^{D\times 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\in\{0,1,*\}^{D\times D}$, the complexity of counting $M$-partitions is the same as the related problem of counting list $M$-partitions.
[3] M. Chudnovsky. Berge trigraphs and their applications. PhD thesis, Princeton University, 2003.
[4] M. Dyer and C. Greenhill. The complexity of counting graph homomorphisms. Random Struct. Algorithms, 17(3-4):260-289, 2000.
[5] T. Feder, P. Hell, S. Klein, and R. Motwani. Complexity of graph partition problems. In Proc. 31st ACM Symposium on Theory of Computing (STOC 1999), pages 464-472. ACM, 1999.
[6] T. Feder, P. Hell, S. Klein, and R. Motwani. List partitions. SIAM J. Discrete Math., 16(3):449-478, 2003.
[7] A. G¨obel, L. A. Goldberg, C. McQuillan, D. Richerby, and T. Yamakami. Counting list matrix partitions of graphs. In Proc. 29th Conference on Computational Complexity (CCC 2014), pages 56-65. IEEE, 2014. Full version: ArXiv CoRR abs/1306.5176.
[8] P. Hell, M. Hermann, and M. Nevisi. Counting partitions of graphs. In Proc. 23rd International Symposium on Algorithms and Computation (ISAAC 2012), volume 7676 of LNCS, pages 227-236. Springer, 2012.
[9] P. Hell and J. Neˇsetˇril. Counting list homomorphisms and graphs with bounded degrees. In J. Neˇsetˇril and P. Winkler, editors, Graphs, Morphisms and Statistical Physics, volume 63 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 105-112, 2004.
[10] P. Hell and J. Neˇsetˇril. Graphs and Homomorphisms. Oxford University Press, 2004.
[11] J. S. Provan and M. O. Ball. The complexity of counting cuts and computing the probability that a graph is connected. SIAM J. Comput., 12(4):777-788, 1983.
[12] L. G. Valiant. The complexity of enumeration and reliability problems. SIAM J. Comput., 8(3):410-421, 1979.