Counting Homomorphisms to Square-Free Graphs, Modulo 2

DOI10.1007/978-3-662-47672-7_52zbMath1440.68187arXiv1501.07539OpenAlexW2499446130MaRDI QIDQ3448822

Andreas Göbel, Leslie Ann Goldberg, David Richerby

Publication date: 27 October 2015

Published in: ACM Transactions on Computation Theory, Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1501.07539

zbMATH Keywords

graph homomorphismcounting modulo 2parity complexity dichotomy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Unnamed Item, Counting Constraint Satisfaction Problems., Unnamed Item, The Complexity of Counting Surjective Homomorphisms and Compactions, Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2

Cites Work

• Unnamed Item
• Unnamed Item
• Holographic algorithms: from art to science
• On the construction of parallel computers from various basis of Boolean functions
• On the complexity of H-coloring
• Square-free perfect graphs.
• Computational complexity of counting problems on 3-regular planar graphs
• The complexity of partition functions
• The complexity of counting homomorphisms to cactus graphs modulo 2
• The complexity of parity graph homomorphism: an initial investigation
• On Searching for Small Kochen-Specker Vector Systems
• PP is as Hard as the Polynomial-Time Hierarchy
• Approximately Counting Locally-Optimal Structures
• A Complexity Dichotomy for Partition Functions with Mixed Signs
• The complexity of satisfiability problems
• Operations with structures