Sampling and Counting Acyclic Orientations in Chordal Graphs (Student Abstract)


  • Wenbo Sun Rochester Institute of Technology



DAG, Acyclic Orientation, Structure Learning, Chordal Graphs, Sampling And Counting


Sampling of chordal graphs and various types of acyclic orientations over chordal graphs plays a central role in several AI applications such as causal structure learning. For a given undirected graph, an acyclic orientation is an assignment of directions to all of its edges which makes the resulting directed graph cycle-free. Sampling is often closely related to the corresponding counting problem. Counting of acyclic orientations of a given chordal graph can be done in polynomial time, but the previously known techniques do not seem to lead to a corresponding (efficient) sampler. In this work, we propose a dynamic programming framework which yields a counter and a uniform sampler, both of which run in (essentially) linear time. An interesting feature of our sampler is that it is a stand-alone algorithm that, unlike other DP-based samplers, does not need any preprocessing which determines the corresponding counts.




How to Cite

Sun, W. (2022). Sampling and Counting Acyclic Orientations in Chordal Graphs (Student Abstract). Proceedings of the AAAI Conference on Artificial Intelligence, 36(11), 13061-13062.