The complexity of counting homomorphisms seen from the other side
DOI10.1016/J.TCS.2004.08.008zbMATH Open1086.68054OpenAlexW2049559029MaRDI QIDQ706636FDOQ706636
Authors: Peter Jonsson, Víctor 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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Exact enumeration problems, generating functions (05A15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- A partial k-arboretum of graphs with bounded treewidth
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Towards a dichotomy theorem for the counting constraint satisfaction problem
- 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
- When is the evaluation of conjunctive queries tractable?
- Complexity of generalized satisfiability counting problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (40)
- Counting edge-injective homomorphisms and matchings on restricted graph classes
- On recognizing graphs by numbers of homomorphisms
- Lov\'asz Meets Weisfeiler and Leman
- The Complexity of Homomorphism Indistinguishability
- Counting induced subgraphs: an algebraic approach to \(\#\)W[1]-hardness
- Title not available (Why is that?)
- Approximability of clausal constraints
- Structural tractability of counting of solutions to conjunctive queries
- Tractable counting of the answers to conjunctive queries
- The complexity of weighted counting for acyclic conjunctive queries
- Towards a dichotomy theorem for the counting constraint satisfaction problem
- Some hard families of parameterized counting problems
- Counting Homomorphic Cycles in Degenerate Graphs
- Counting Small Induced Subgraphs with Hereditary Properties
- Parameterised counting in logspace
- Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights
- Counting Small Induced Subgraphs Satisfying Monotone Properties
- Some complete and intermediate polynomials in algebraic complexity theory
- Parameterized counting of partially injective homomorphisms
- The parameterised complexity of counting connected subgraphs and graph motifs
- Counting subgraphs in somewhere dense graphs
- Answer Counting under Guarded TGDs
- The homomorphism domination exponent
- Monotone arithmetic complexity of graph homomorphism polynomials
- Structural tractability of enumerating CSP solutions
- Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices
- The complexity of counting homomorphisms to cactus graphs modulo 2
- Title not available (Why is that?)
- On planar valued CSPs
- Bounded Tree-Width and CSP-Related Problems
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- Title not available (Why is that?)
- Counting induced subgraphs: a topological approach to \#W[1]-hardness
- Parameterized Counting and Cayley Graph Expanders
- The challenges of unbounded treewidth in parameterised subgraph counting problems
- Counting Subgraphs in Degenerate Graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Counting Answers to Existential Questions
- Parameterised and fine-grained subgraph counting, modulo 2
This page was built for publication: The complexity of counting homomorphisms seen from the other side
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q706636)
