FPT Algorithms to Enumerate and Count Acyclic and Totally Cyclic Orientations
Farley Soares Oliveira, Hidefumi Hiraishi, Hiroshi Imai · Electronic Notes in Theoretical Computer Science · 2019
In this paper, we deal with counting and enumerating problems for two types of graph orientations: acyclic and totally cyclic orientations. Counting is known to be #P-hard for both of them. To circumvent this issue, we propose Fixed Parameter Tractable (FPT) algorithms. For the enumeration task, we construct a Binary Decision Diagram (BDD) to represent all orientations of the two kinds, instead of explicitly enumerating them. We prove that the running time of this construction is bounded by O*(2pw2/4+o(pw2)) with respect to the pathwidth pw. We then develop faster FPT algorithms to count acyclic and totally acyclic orientations, running in O*(2bw2/2+o(bw2)) time, where bw denotes the branch-width of the given graph. These counting algorithms are obtained by applying the observations in our enumerating algorithm to branch decomposition.