Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


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.


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.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Dyer, M; Goldberg, LA; Richerby, D (2016)
Publisher: Elsevier
Journal: Discrete Applied Mathematics
Languages: English
Types: Article
Subjects: Computer Science - Computational Complexity
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.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [1] A. Bulatov. The complexity of the counting constraint satisfaction problem. J. ACM, 60(5):34:1-34:41, 2013.
    • [2] A. Bulatov and V. Dalmau. Towards a dichotomy theorem for the counting constraint satisfaction problem. Inform. Comput., 205(5):651-678, 2007.
    • [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.
  • No related research data.
  • Discovered through pilot similarity algorithms. Send us your feedback.

    Title Year Similarity

    Almost all friendly matrices have many obstructions


Share - Bookmark

Funded by projects

  • EC | MCC

Cite this article