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