scientific article; zbMATH DE number 7561703

DOI10.4230/LIPIcs.MFCS.2019.59MaRDI QIDQ5092422

Andrei A. Bulatov, Amirhossein Kazeminia

Publication date: 21 July 2022

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

graph homomorphismmodular countingcomputational hardness

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

Complexity of correspondence \(H\)-colourings ⋮ Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• On the complexity of H-coloring
• The complexity of approximating complex-valued Ising and Tutte partition functions
• The complexity of partition functions
• Approximately Counting $H$-Colorings is $\#\mathrm{BIS}$-Hard
• The complexity of counting homomorphisms to cactus graphs modulo 2
• The complexity of parity graph homomorphism: an initial investigation
• Counting Homomorphisms to Square-Free Graphs, Modulo 2
• The Complexity of Enumeration and Reliability Problems
• A Complexity Trichotomy for Approximately Counting List H -Colorings
• A Complexity Dichotomy for Partition Functions with Mixed Signs
• Graph Homomorphisms with Complex Values: A Dichotomy Theorem

This page was built for publication: