License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2019.59
URN: urn:nbn:de:0030-drops-110032
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11003/
Go to the corresponding LIPIcs Volume Portal

Kazeminia, Amirhossein ; Bulatov, Andrei A.

Counting Homomorphisms Modulo a Prime Number

pdf-format:
LIPIcs-MFCS-2019-59.pdf (0.6 MB)

Abstract

Counting problems in general and counting graph homomorphisms in particular have numerous applications in combinatorics, computer science, statistical physics, and elsewhere. One of the most well studied problems in this area is #GraphHom(H) - the problem of finding the number of homomorphisms from a given graph G to the graph H. Not only the complexity of this basic problem is known, but also of its many variants for digraphs, more general relational structures, graphs with weights, and others. In this paper we consider a modification of #GraphHom(H), the #_{p}GraphHom(H) problem, p a prime number: Given a graph G, find the number of homomorphisms from G to H modulo p. In a series of papers Faben and Jerrum, and Göbel et al. determined the complexity of #_{2}GraphHom(H) in the case H (or, in fact, a certain graph derived from H) is square-free, that is, does not contain a 4-cycle. Also, Göbel et al. found the complexity of #_{p}GraphHom(H) when H is a tree for an arbitrary prime p. Here we extend the above result to show that the #_{p}GraphHom(H) problem is #_{p}P-hard whenever the derived graph associated with H is square-free and is not a star, which completely classifies the complexity of #_{p}GraphHom(H) for square-free graphs H.

BibTeX - Entry

@InProceedings{kazeminia_et_al:LIPIcs:2019:11003,
  author =	{Amirhossein Kazeminia and Andrei A. Bulatov},
  title =	{{Counting Homomorphisms Modulo a Prime Number}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{59:1--59:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11003},
  URN =		{urn:nbn:de:0030-drops-110032},
  doi =		{10.4230/LIPIcs.MFCS.2019.59},
  annote =	{Keywords: graph homomorphism, modular counting, computational hardness}
}

Keywords: graph homomorphism, modular counting, computational hardness
Collection: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Issue Date: 2019
Date of publication: 20.08.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI