Sampling and Counting Acyclic Orientations in Chordal Graphs (Student Abstract)
Keywords:DAG, Acyclic Orientation, Structure Learning, Chordal Graphs, Sampling And Counting
AbstractSampling 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. https://doi.org/10.1609/aaai.v36i11.21667
AAAI Student Abstract and Poster Program