Counting Homomorphisms to Square-Free Graphs, Modulo 2

Counting Homomorphisms to Square-Free Graphs, Modulo 2

Show other versions (1)

We study the problem ⊕HomsTo<em>H</em> of counting, modulo 2, the homomorphisms from an input graph to a fixed undirected graph <em>H</em>. A characteristic feature of modular counting is that cancellations make wider classes of instances tractable than is the case for exact...

Disgrifiad llawn

Manylion Llyfryddiaeth
Prif Awduron:	Gobel, A, Goldberg, L, Richerby, D
Fformat:	Conference item
Iaith:	English
Cyhoeddwyd:	Schloss Dagstuhl - LZI GmbH 2015

Eitemau Tebyg

Counting homomorphisms to square-free graphs, modulo 2
gan: Goldberg, L, et al.
Cyhoeddwyd: (2016)

The Complexity of Counting Homomorphisms to Cactus Graphs Modulo 2
gan: Göbel, A, et al.
Cyhoeddwyd: (2013)

Counting homomorphisms to K4-minor-free graphs, modulo 2
gan: Focke, J, et al.
Cyhoeddwyd: (2021)

Counting homomorphisms to K4-minor-free graphs, modulo 2
gan: Focke, J, et al.
Cyhoeddwyd: (2021)

Counting, modular counting and graph homomorphisms
gan: Magkakis, A
Cyhoeddwyd: (2016)

Counting list matrix partitions of graphs
gan: Göbel, A, et al.
Cyhoeddwyd: (2015)

Counting list matrix partitions of graphs
gan: Göbel, A, et al.
Cyhoeddwyd: (2013)

The complexity of approximately counting retractions to square-free graphs
gan: Focke, J, et al.
Cyhoeddwyd: (2021)

Parameterised and fine-grained subgraph counting, modulo 2
gan: Goldberg, L, et al.
Cyhoeddwyd: (2023)

Parameterised and fine-grained subgraph counting, modulo 2
gan: Goldberg, LA, et al.
Cyhoeddwyd: (2023)

Counting 4 × 4 matrix partitions of graphs
gan: Dyer, M, et al.
Cyhoeddwyd: (2016)

The complexity of counting surjective homomorphisms and compactions
gan: Focke, J, et al.
Cyhoeddwyd: (2017)

The complexity of counting surjective homomorphisms and compactions
gan: Focke, J, et al.
Cyhoeddwyd: (2019)

Counting edge-injective homomorphisms and matchings on restricted graph classes
gan: Curticapean, R, et al.
Cyhoeddwyd: (2018)

Counting edge-injective homomorphisms and matchings on restricted graph classes
gan: Curticapean, R, et al.
Cyhoeddwyd: (2017)

On graph decompositions modulo k
gan: Scott, A
Cyhoeddwyd: (1997)

Parameterized counting of partially injective homomorphisms
gan: Roth, M
Cyhoeddwyd: (2021)

Graph homomorphisms between trees
gan: Csikvari, Peter, et al.
Cyhoeddwyd: (2015)

Graph homomorphisms for quantum players
gan: Mančinska, Laura, et al.
Cyhoeddwyd: (2018)

On the complexity of counting homomorphisms under surjectivity constraints
gan: Focke, J
Cyhoeddwyd: (2020)

Faster exponential-time algorithms for approximately counting independent sets
gan: Goldberg, L, et al.
Cyhoeddwyd: (2021)

Graph homomorphisms via vector colorings
gan: Godsil, Chris, et al.
Cyhoeddwyd: (2020)

The Bipartite Swapping Trick on Graph Homomorphisms
gan: Zhao, Yufei
Cyhoeddwyd: (2011)

Counting and finding homomorphisms is universal for parameterized complexity theory
gan: Roth, M, et al.
Cyhoeddwyd: (2020)

Delocalization of Uniform Graph Homomorphisms from Z2 to Z
gan: Chandgotia, Nishant, et al.
Cyhoeddwyd: (2021)

A dichotomy for homomorphism−closed queries on probabilistic graphs
gan: Amarilli, A, et al.
Cyhoeddwyd: (2020)

Counting subgraphs in somewhere dense graphs
gan: Bressan, M, et al.
Cyhoeddwyd: (2023)

Counting subgraphs in somewhere dense graphs
gan: Bressan, M, et al.
Cyhoeddwyd: (2024)

Counting restricted homomorphisms via Möbius inversion over matroid lattices
gan: Roth, M
Cyhoeddwyd: (2017)

Counting 2-circulant graphs /
gan: 306081 Chia, Gek-Ling, et al.
Cyhoeddwyd: (1981)

Modulo-N equalizer
gan: 383014 Halim Abd. Aziz
Cyhoeddwyd: (1977)

Homomorphisms from automorphism groups of free groups
gan: Bridson, M, et al.
Cyhoeddwyd: (2002)

Counting disk graphs.
gan: McDiarmid, C, et al.
Cyhoeddwyd: (2011)

On metric properties of maps between Hamming spaces and related graph homomorphisms
gan: Polyanskiy, Yury
Cyhoeddwyd: (2019)

A framework for Satisfiability Modulo Theories.
gan: Kroening, D, et al.
Cyhoeddwyd: (2009)

The distribution of alpha p modulo one
gan: Heath-Brown, D, et al.
Cyhoeddwyd: (2002)

LATTICES OF HOMOMORPHISMS
gan: Davey, B, et al.
Cyhoeddwyd: (1986)

Modulo video recovery with deep learning
gan: Li,Zike
Cyhoeddwyd: (2024)

On the ranks of partitions modulo certain integers
gan: Hong, Nankun
Cyhoeddwyd: (2020)

The distribution of αp modulo one
gan: Heath-Brown, DR, et al.
Cyhoeddwyd: (2002)