10
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.