Given an undirected graph $G$, an acyclic orientation of $G$ is choice of orientation for each edge of $G$ (turning each edge into an arc) such that the resulting directed graph has no directed cycles.
Question: Given an undirected graph $G$ on $n$ nodes, what is the fastest known algorithm for counting the number of acyclic orientations of $G$?
I believe this problem can be solved in $2^n\text{poly}(n)$ time using existing inclusion-exclusion or fast subset convolution ideas (although I haven't verified the details of such an algorithm), but I'm curious to know if there an algorithm solving this problem in $c^n$ time for some constant $c < 2$.
