Title
Authors: Robert Ganian, Thekla Hamm, Topi Talvitie10136-10143
AAAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our main empirical contribution is a new algorithm which outperforms previously known exact algorithms for the considered problem by a significant margin. On the empirical side, we show that Anon MAO vastly outperforms previously known exact algorithms for #MAO. We compared the practical performance of the Anon MAO algorithm to the state-of-the-art algorithms, notably: Root Picking Dynamic Programming: The root picking algorithm due to He, Jia, and Yu (2015) with the dynamic programming speedup (Talvitie and Koivisto 2019). He and Yu 2016: The algorithm by He and Yu (2016) based on recursively computing polynomials P(m) for core graphs such that P(m)m! is the number of MAOs when we add m dominating vertices. Dynamic Programming in Tree Decomposition: The algorithm by Talvitie and Koivisto (2019) based on dynamic programming on the clique-tree with time-complexity in O(2kk!k2n) parameterised by the treewidth k. The results are shown in Figure 1. |
| Researcher Affiliation | Academia | 1Vienna University of Technology, Austria, Email: rganian@gmail.com, thamm@ac.tuwien.ac.at 2University of Helsinki, Finland, Email: topi.talvitie@helsinki.fi |
| Pseudocode | Yes | Algorithm 1: Root Picking; Algorithm 2: Anon MAO |
| Open Source Code | Yes | We implemented2 Anon MAO using C++, and for the other algorithms, we used the C++ implementations of Talvitie and Koivisto (2019). 2github.com/ttalvitie/efficient-markov-equivalent-dag-counting |
| Open Datasets | No | The paper describes a process for generating instances: 'The instances are generated by first generating a tree of n vertices by successively adding each vertex as a neighbour to a randomly chosen previously added vertex, and then, as long as the graph has less than rn edges, repeatedly choosing a random pair of elements and adding an edge between them if the resulting graph is chordal.' This describes a generation procedure rather than citing or linking to a pre-existing, publicly available dataset. |
| Dataset Splits | No | The paper describes generating graph instances and running algorithms on them, but it does not specify training, validation, or test dataset splits, as it is not a machine learning paper involving typical data partitioning for model training. |
| Hardware Specification | No | The paper mentions that 'All the implementations use only one thread of execution' but does not specify any particular hardware components like CPU or GPU models, memory, or specific computing environments. |
| Software Dependencies | No | The paper mentions 'implemented2 Anon MAO using C++' and 'C++ implementations of Talvitie and Koivisto (2019)' but does not provide specific version numbers for C++ compilers, libraries, or any other software dependencies. |
| Experiment Setup | Yes | For each number of vertices 32 n 1024 and density parameter 2 r 32, we generated 50 UCCG instances, and ran each algorithm for each instance. The time limit was set to 10 minutes and the memory limit to 32 gigabytes. |