The complexity of counting homomorphisms to cactus graphs modulo 2

DOI10.1145/2635825zbMath1347.68181arXiv1307.0556OpenAlexW2030999876MaRDI QIDQ2828223

David Richerby, Leslie Ann Goldberg, Andreas Göbel

Publication date: 24 October 2016

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

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

zbMATH Keywords

graph homomorphismcactus graphcounting modulo 2parity complexity dichotomy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Enumeration in graph theory (05C30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Counting Homomorphisms to Square-Free Graphs, Modulo 2, Unnamed Item, Counting Constraint Satisfaction Problems., Unnamed Item, Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2

Cites Work

• Unnamed Item
• On the construction of parallel computers from various basis of Boolean functions
• Complexity of generalized satisfiability counting problems
• Efficient algorithms for center problems in cactus networks
• The complexity of partition functions
• The complexity of parity graph homomorphism: an initial investigation
• Centdian Computation in Cactus Graphs
• Another Proof of Cauchy's Group Theorem
• PP is as Hard as the Polynomial-Time Hierarchy
• The Complexity of Weighted Boolean #CSP
• A Complexity Dichotomy for Partition Functions with Mixed Signs
• Operations with structures
• On the Number of Husimi Trees
• The Complexity of Symmetric Boolean Parity Holant Problems
• Graph Homomorphisms with Complex Values: A Dichotomy Theorem