Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs
Authors: Marcel Wienöbst, Max Bannach, Maciej Liskiewicz12198-12206
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experimental results show that the algorithms significantly outperform state-of-the-art methods. |
| Researcher Affiliation | Academia | Marcel Wien obst, Max Bannach, Maciej Li skiewicz Institute of Theoretical Computer Science, University of L ubeck, Germany {wienoebst,bannach,liskiewi}@tcs.uni-luebeck.de |
| Pseudocode | Yes | Algorithm 1: A modified version of the lexicographic BFS... Algorithm 2: The Clique-Picking algorithm computes the number of acyclic moral orientations of a UCCG G. |
| Open Source Code | Yes | The source code and the supplementary material are available at https://github.com/mwien/Clique Picking. |
| Open Datasets | Yes | Figure 2 shows the run time of the four algorithms on random chordal graphs details of the random graph generation and further experiments can be found in the supplementary material. We chose the random subtree intersection method (left plot in Fig. 2) as it generates a broad range of chordal graphs (Seker et al. 2017); and we complemented these with random interval graphs (right plot) as Anon MAO runs provably in polynomial time on this subclass of chordal graphs (Ganian, Hamm, and Talvitie 2020). |
| Dataset Splits | No | The paper does not mention training, validation, or test splits, as the experiments involve running algorithms on generated graphs rather than training a machine learning model with data partitions. |
| Hardware Specification | No | The paper does not provide specific details about the hardware used for the experiments. |
| Software Dependencies | No | The paper does not specify any software dependencies with version numbers (e.g., Python, PyTorch, specific solvers). |
| Experiment Setup | Yes | Figure 2 shows the run time of the four algorithms on random chordal graphs details of the random graph generation and further experiments can be found in the supplementary material4. We chose the random subtree intersection method (left plot in Fig. 2) as it generates a broad range of chordal graphs (Seker et al. 2017); and we complemented these with random interval graphs (right plot) as Anon MAO runs provably in polynomial time on this subclass of chordal graphs (Ganian, Hamm, and Talvitie 2020). |