Counting 4×4 matrix partitions of graphs

Article, Preprint English OPEN
Dyer, M ; Goldberg, LA ; Richerby, D (2016)
  • Publisher: Elsevier
  • Journal: Discrete Applied Mathematics, volume 213 (issn: 0166-218X)
  • Related identifiers: doi: 10.1016/j.dam.2016.05.001
  • Subject: 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.
  • References (12)
    12 references, page 1 of 2

    [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.

  • Similar Research Results (1)
  • Metrics
    No metrics available
Share - Bookmark