Abstract
We study the problem \(\oplus \textsc {HomsTo}{H}\) of counting, modulo 2, the homomorphisms from an input graph to a fixed undirected graph H. A characteristic feature of modular counting is that cancellations make wider classes of instances tractable than is the case for exact (non-modular) counting, so subtle dichotomy theorems can arise. We show the following dichotomy: for any H that contains no 4-cycles, \(\oplus \textsc {HomsTo}{H}\) is either in polynomial time or is \(\oplus \mathrm {P}\)-complete. This partially confirms a conjecture of Faben and Jerrum that was previously only known to hold for trees and for a restricted class of tree-width-2 graphs called cactus graphs. We confirm the conjecture for a rich class of graphs including graphs of unbounded tree-width. In particular, we focus on square-free graphs, which are graphs without 4-cycles. These graphs arise frequently in combinatorics, for example in connection with the strong perfect graph theorem and in certain graph algorithms. Previous dichotomy theorems required the graph to be tree-like so that tree-like decompositions could be exploited in the proof. We prove the conjecture for a much richer class of graphs by adopting a much more general approach.
Theorem numbering in this extended abstract matches matches the full version: ArXiv, CoRR, abs/1501.07539. The research leading to these results has received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007–2013) ERC grant agreement no. 334828. The paper reflects only the authors’ views and not the views of the ERC or the European Commission. The European Union is not liable for any use that may be made of the information contained therein.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arends, F., Ouaknine, J., Wampler, C.W.: On searching for small Kochen-Specker vector systems. In: Kolman, P., Kratochvíl, J. (eds.) WG 2011. LNCS, vol. 6986, pp. 23–34. Springer, Heidelberg (2011)
Bulatov, A.A., Grohe, M.: The complexity of partition functions. Theor. Comput. Sci. 348(2–3), 148–186 (2005)
Cai, J.-Y., Lu, P.: Holographic algorithms: From art to science. J. Comput. Syst. Sci. 77(1), 41–61 (2011)
Conforti, M., Cornuéjols, G., Vušković, K.: Square-free perfect graphs. J. Combin. Theory Ser. B 90(2), 257–307 (2004)
Dyer, M.E., Greenhill, C.S.: The complexity of counting graph homomorphisms. Random Struct. Algorithms 17(3–4), 260–289 (2000)
Faben, J., Jerrum, M.: The complexity of parity graph homomorphism: an initial investigation. Theor. Comput. 11, 35–57 (2015)
Göbel, A., Goldberg, L.A., Richerby, D.: The complexity of counting homomorphisms to cactus graphs modulo 2. ACM T. Comput. Theory, 6(4), article 17 (2014)
Goldberg, L.A., Grohe, M., Jerrum, M., Thurley, M.: A complexity dichotomy for partition functions with mixed signs. SIAM J. Comput. 39(7), 3336–3402 (2010)
Goldberg, L.A., Gysel, R., Lapinskas, J.: Approximately counting locally-optimal structures. CoRR, abs/1411.6829 (2014)
Goldschlager, L.M., Parberry, I.: On the construction of parallel computers from various bases of Boolean functions. Theor. Comput. Sci. 43, 43–58 (1986)
Hell, P., Nešetřil, J.: On the complexity of \(H\)-coloring. J. Comb. Theory, Ser. B 48(1), 92–110 (1990)
Lovász, L.: Operations with structures. Acta Math. Acad. Sci. Hungar. 18(3–4), 321–328 (1967)
Papadimitriou, C.H., Zachos, S.: Two remarks on the power of counting. In: Cremers, A.B., Kriegel, H.-P. (eds.) Theoretical Computer Science. LNCS, vol. 145, pp. 269–275. Springer, Heidelberg (1982)
Schaefer, T.J.: The complexity of satisfiability problems. In: Proc. 10th Annual ACM Symposium on Theory of Computing (STOC 1978), pp. 216–226. ACM Press (1978)
Toda, S.: PP is as hard as the polynomial-time hierarchy. SIAM J. Comput. 20(5), 865–877 (1991)
Valiant, L.G.: Accidental algorithms. In: Proc. 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pp. 509–517. IEEE (2006)
Xia, M., Zhang, P., Zhao, W.: Computational complexity of counting problems on \(3\)-regular planar graphs. Theoret. Comput. Sci. 384(1), 111–125 (2007)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Göbel, A., Goldberg, L.A., Richerby, D. (2015). Counting Homomorphisms to Square-Free Graphs, Modulo 2. In: Halldórsson, M., Iwama, K., Kobayashi, N., Speckmann, B. (eds) Automata, Languages, and Programming. ICALP 2015. Lecture Notes in Computer Science(), vol 9134. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-47672-7_52
Download citation
DOI: https://doi.org/10.1007/978-3-662-47672-7_52
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-47671-0
Online ISBN: 978-3-662-47672-7
eBook Packages: Computer ScienceComputer Science (R0)