Counting Homomorphisms to K₄-Minor-Free Graphs, Modulo 2

DOI10.1137/20M1382921MaRDI QIDQ5013574zbMATH OpenFDO

Authors Jacob Focke, Leslie Ann Goldberg, Marc Roth, S. Zivny

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

counting complexitycounting modulo 2graph homomorphismsparity complexity dichotomy

Mathematics Subject Classification ID

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

Recommendations

• Homomorphism bounds and edge-colourings of \(K_{4}\)-minor-free graphs
• A characterization of \(K_{2,4}\)-minor-free graphs
• scientific article; zbMATH DE number 6691415
• Homomorphism bounds of signed bipartite \(K_4\)-minor-free graphs and edge-colorings of \(2k\)-regular \(K_4\)-minor-free multigraphs
• Vertex partitions of \(K_{4,4}\)-minor free graphs
• Counting graph homomorphisms involving complete graphs
• Counting graph homomorphisms
• scientific article; zbMATH DE number 554189

Cites work

• A Complexity Trichotomy for Approximately Counting List H -Colorings
• Approximately counting \(H\)-colorings is \(\#\)BIS-hard
• Conjunctive-query containment and constraint satisfaction
• Counting \(H-\)colorings of partial \(k-\)trees
• Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory
• Counting graph homomorphisms
• Counting homomorphisms modulo a prime number
• Counting homomorphisms to trees modulo a prime
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• Graph homomorphisms and phase transitions
• Graph minor theory
• Homomorphisms are a good basis for counting small subgraphs
• scientific article; zbMATH DE number 1545676 (Why is no real title available?)
• scientific article; zbMATH DE number 3799016 (Why is no real title available?)
• List homomorphisms to reflexive graphs
• On the complexity of k-SAT
• On the complexity of H-coloring
• On the construction of parallel computers from various basis of Boolean functions
• Perfect Elimination and Chordal Bipartite Graphs
• PP is as Hard as the Polynomial-Time Hierarchy
• Reducibility among combinatorial problems
• The complexity of approximately counting retractions
• The complexity of approximately counting tree homomorphisms
• The complexity of counting homomorphisms to cactus graphs modulo 2
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The complexity of parity graph homomorphism: an initial investigation
• The Exponential Time complexity of counting (quantum) graph homomorphisms
• The Parameterized Complexity of Counting Problems
• The relative complexity of approximate counting problems
• Topology of series-parallel networks
• When is the evaluation of conjunctive queries tractable?

Cited in

(3)

• A Brooks-type bound for squares of \(K_{4}\)-minor-free graphs
• Homomorphism bounds and edge-colourings of \(K_{4}\)-minor-free graphs
• scientific article; zbMATH DE number 6691415 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5013574)