A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights

DOI10.1007/s00037-019-00184-5zbMath1429.68079arXiv1008.0915OpenAlexW2941701579WikidataQ128007646 ScholiaQ128007646MaRDI QIDQ2323358

Xi Chen, Jin-Yi Cai

Publication date: 30 August 2019

Published in: Computational Complexity (Search for Journal in Brave)

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

zbMATH Keywords

decidabilitygraph homomorphismdichotomy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

A dichotomy for bounded degree graph homomorphisms with nonnegative weights

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of weighted and unweighted \(\#\)CSP
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• On the complexity of H-coloring
• The complexity of partition functions
• An Effective Dichotomy for the Counting Constraint Satisfaction Problem
• On the complexity of #CSP
• Reflection positivity, rank connectivity, and homomorphism of graphs
• The Complexity of the Counting Constraint Satisfaction Problem
• On counting homomorphisms to directed acyclic graphs
• Algorithms in Algebraic Number Theory
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• A Complexity Dichotomy for Partition Functions with Mixed Signs
• The complexity of the counting constraint satisfaction problem
• Complexity of counting CSP with complex weights
• A complete dichotomy rises from the capture of vanishing signatures
• Graph Homomorphisms with Complex Values: A Dichotomy Theorem