The complexity of counting homomorphisms seen from the other side

DOI10.1016/j.tcs.2004.08.008zbMath1086.68054OpenAlexW2049559029MaRDI QIDQ706636

Peter Jonsson, Victor Dalmau

Publication date: 9 February 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.08.008

zbMATH Keywords

Computational complexityCountingHomomorphismRelational structure

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Exact enumeration problems, generating functions (05A15) Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (36)

Structural tractability of counting of solutions to conjunctive queries ⋮ Counting Subgraphs in Degenerate Graphs ⋮ Counting induced subgraphs: an algebraic approach to \(\#\)W[1-hardness] ⋮ Some complete and intermediate polynomials in algebraic complexity theory ⋮ Unnamed Item ⋮ Counting Small Induced Subgraphs Satisfying Monotone Properties ⋮ On planar valued CSPs ⋮ Lov\'asz Meets Weisfeiler and Leman ⋮ Towards a dichotomy theorem for the counting constraint satisfaction problem ⋮ Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights ⋮ Tractable counting of the answers to conjunctive queries ⋮ The complexity of weighted counting for acyclic conjunctive queries ⋮ Counting Homomorphic Cycles in Degenerate Graphs ⋮ Answer Counting under Guarded TGDs ⋮ Monotone arithmetic complexity of graph homomorphism polynomials ⋮ Parameterised counting in logspace ⋮ The challenges of unbounded treewidth in parameterised subgraph counting problems ⋮ Parameterised and fine-grained subgraph counting, modulo 2 ⋮ Counting Small Induced Subgraphs with Hereditary Properties ⋮ Parameterized Counting and Cayley Graph Expanders ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Bounded Tree-Width and CSP-Related Problems ⋮ The parameterised complexity of counting connected subgraphs and graph motifs ⋮ Approximability of clausal constraints ⋮ On recognizing graphs by numbers of homomorphisms ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parameterized counting of partially injective homomorphisms ⋮ The Complexity of Homomorphism Indistinguishability ⋮ Counting Answers to Existential Questions ⋮ Some Hard Families of Parameterized Counting Problems ⋮ Counting edge-injective homomorphisms and matchings on restricted graph classes ⋮ Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices ⋮ Counting induced subgraphs: a topological approach to \#W[1-hardness] ⋮ Structural tractability of enumerating CSP solutions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• A partial k-arboretum of graphs with bounded treewidth
• On the algebraic structure of combinatorial problems
• Quickly excluding a planar graph
• A comparison of structural CSP decomposition methods
• Conjunctive-query containment and constraint satisfaction
• Complexity of generalized satisfiability counting problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• When is the evaluation of conjunctive queries tractable?

This page was built for publication: The complexity of counting homomorphisms seen from the other side