The complexity of counting homomorphisms to cactus graphs modulo 2
From MaRDI portal
Enumeration in graph theory (05C30) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)
Abstract: A homomorphism from a graph G to a graph H is a function from V(G) to V(H) that preserves edges. Many combinatorial structures that arise in mathematics and computer science can be represented naturally as graph homomorphisms and as weighted sums of graph homomorphisms. In this paper, we study the complexity of counting homomorphisms modulo 2. The complexity of modular counting was introduced by Papadimitriou and Zachos and it has been pioneered by Valiant who famously introduced a problem for which counting modulo 7 is easy but counting modulo 2 is intractable. Modular counting provides a rich setting in which to study the structure of homomorphism problems. In this case, the structure of the graph H has a big influence on the complexity of the problem. Thus, our approach is graph-theoretic. We give a complete solution for the class of cactus graphs, which are connected graphs in which every edge belongs to at most one cycle. Cactus graphs arise in many applications such as the modelling of wireless sensor networks and the comparison of genomes. We show that, for some cactus graphs H, counting homomorphisms to H modulo 2 can be done in polynomial time. For every other fixed cactus graph H, the problem is complete for the complexity class parity-P which is a wide complexity class to which every problem in the polynomial hierarchy can be reduced (using randomised reductions). Determining which H lead to tractable problems can be done in polynomial time. Our result builds upon the work of Faben and Jerrum, who gave a dichotomy for the case in which H is a tree.
Recommendations
- scientific article; zbMATH DE number 6691415
- scientific article; zbMATH DE number 1545676
- scientific article; zbMATH DE number 1445311
- Complexity classification of counting graph homomorphisms modulo a prime number
- scientific article; zbMATH DE number 4162940
- On Counting Homomorphisms to Directed Acyclic Graphs
- Counting graph homomorphisms
- The complexity of counting homomorphisms seen from the other side
Cites work
- A Complexity Dichotomy for Partition Functions with Mixed Signs
- Another Proof of Cauchy's Group Theorem
- Centdian computation in cactus graphs
- Complexity of generalized satisfiability counting problems
- Efficient algorithms for center problems in cactus networks
- Graph homomorphisms with complex values: a dichotomy theorem (extended abstract)
- scientific article; zbMATH DE number 1545676 (Why is no real title available?)
- On the construction of parallel computers from various basis of Boolean functions
- On the Number of Husimi Trees
- Operations with structures
- PP is as Hard as the Polynomial-Time Hierarchy
- The complexity of parity graph homomorphism: an initial investigation
- The complexity of partition functions
- The complexity of symmetric Boolean parity Holant problems
- The Complexity of Weighted Boolean #CSP
Cited in
(8)- scientific article; zbMATH DE number 6691415 (Why is no real title available?)
- Counting constraint satisfaction problems
- Counting homomorphisms to trees modulo a prime
- Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2
- Counting homomorphisms modulo a prime number
- Counting homomorphisms to trees modulo a prime
- On counting (quantum-)graph homomorphisms in finite fields of prime order
- Modular counting CSP: reductions and algorithms
This page was built for publication: The complexity of counting homomorphisms to cactus graphs modulo 2
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2828223)
