Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2

Stanislav Živný, Marc Roth, Jacob Focke, Leslie Ann Goldberg

Publication date: 1 December 2021

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

graph homomorphisms counting complexity counting modulo 2 parity complexity dichotomy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
On the construction of parallel computers from various basis of Boolean functions
On the complexity of H-coloring
List homomorphisms to reflexive graphs
Graph homomorphisms and phase transitions
Conjunctive-query containment and constraint satisfaction
Counting $H-$colorings of partial $k-$trees
The relative complexity of approximate counting problems
The Exponential Time complexity of counting (quantum) graph homomorphisms
Topology of series-parallel networks
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
The Complexity of Approximately Counting Tree Homomorphisms
PP is as Hard as the Polynomial-Time Hierarchy
Graph minor theory
Counting Homomorphisms to Square-Free Graphs, Modulo 2
The complexity of homomorphism and constraint satisfaction problems seen from the other side
Perfect Elimination and Chordal Bipartite Graphs
The Parameterized Complexity of Counting Problems
Exponential Time Complexity of the Permanent and the Tutte Polynomial
A Complexity Trichotomy for Approximately Counting List H -Colorings
Homomorphisms are a good basis for counting small subgraphs
Reducibility among Combinatorial Problems
Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory
When is the evaluation of conjunctive queries tractable?
The Complexity of Approximately Counting Retractions
On the complexity of $k$-SAT

This page was built for publication: Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2