We give a dichotomy theorem for the problem of counting homomorphisms to
directed acyclic graphs. $H$ is a fixed directed acyclic graph.
The problem is, given an input digraph $G$, how many homomorphisms are there
from $G$ to $H$. We give a graph-theoretic classification, showing that
for some digraphs $H$, ... more >>>

Borodin, Nielsen, and Rackoff gave a model of greedy-like algorithms for scheduling problems and Angelopoulos and Borodin extended their work to facility location and set cover problems. We generalize their notion to include other optimization problems, and apply the generalized framework to graph problems. Our goal is to define an ... more >>>

We introduce the notion of a plain basis for a co-clone in Post's lattice. Such a basis is a set of relations B such that every constraint C over a relation in the co-clone is logically equivalent to a conjunction of equalities and constraints over B and the same variables ... more >>>