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

Jin-Yi Cai Xi Chen

Published in: Comput. Complex. (2019)

Keyphrases

directed graph
random walk
edge weights
positive and negative
graph structure

maximum flow
strongly connected
linear combination
directed acyclic graph
undirected graph

disjoint paths
shortest path problem
graph theory
first order logic
sensor networks

transitive closure
random variables
datalog programs
special case
search algorithm