Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs
Not on the map. Why?
Abstract (arXiv)
Counting and uniform sampling of directed acyclic graphs (DAGs) from a Markov equivalence class are fundamental tasks in graphical causal analysis. In this paper, we show that these tasks can be performed in polynomial time, solving a long-standing open problem in this area. Our algorithms are effective and easily implementable. Experimental results show that the algorithms significantly outperform state-of-the-art methods.
Key facts. Cited by 14 papers in the map (data through 14 Oct 2026). First posted on arXiv 17 Dec 2020.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 1; 2022: 4; 2023: 4; 2024: 1; 2025: 4.
14 papers.
Sort:
- 2022Causal Structure Learning: a Combinatorial Perspectivecited by 46
- 2022Active Learning for Optimal Intervention Design in Causal Modelscited by 31
- 2023Active causal structure learning with advicecited by 10
- 2022Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs with Applicationscited by 9
- 2023Do we become wiser with time? On causal equivalence with tiered background knowledgecited by 9
- 2022A Unified Experiment Design Approach for Cyclic and Acyclic Causal Modelscited by 7
- 2023Efficient Enumeration of Markov Equivalent DAGscited by 6
- 2025Near-Optimal Experiment Design in Linear non-Gaussian Cyclic Modelscited by 4
- 2021Universal Lower Bound for Learning Causal DAGs with Atomic Interventionscited by 2
- 2025Characterization and Learning of Causal Graphs from Hard Interventionscited by 2
- 2023A Fixed-Parameter Tractable Algorithm for Counting Markov Equivalence Classes with the same Skeletoncited by 1
- 2025Less Greedy Equivalence Searchcited by 1
2 more
- 2025Near-Optimal Experiment Design in Linear non-Gaussian Cyclic Models25 Sep 2025
- 2025Design of Experiment for Discovering Directed Mixed Graph2 Sep 2025
- 2025Less Greedy Equivalence Search27 Jun 2025
- 2025Characterization and Learning of Causal Graphs from Hard Interventions2 May 2025
- 2024Membership Testing in Markov Equivalence Classes via Independence Query Oracles9 Mar 2024
- 2023A Fixed-Parameter Tractable Algorithm for Counting Markov Equivalence Classes with the same Skeleton6 Oct 2023
- 2023Do we become wiser with time? On causal equivalence with tiered background knowledge2 Jun 2023
- 2023Active causal structure learning with advice31 May 2023
- 2023Efficient Enumeration of Markov Equivalent DAGs28 Jan 2023
- 2022Active Learning for Optimal Intervention Design in Causal Models10 Sep 2022
- 2022Causal Structure Learning: a Combinatorial Perspective2 Jun 2022
- 2022A Unified Experiment Design Approach for Cyclic and Acyclic Causal Models20 May 2022
- 2022Causal Structure Learning: a Combinatorial Perspectivecited by 46
- 2022Active Learning for Optimal Intervention Design in Causal Modelscited by 31
- 2023Active causal structure learning with advicecited by 10
- 2022Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs with Applicationscited by 9
- 2023Do we become wiser with time? On causal equivalence with tiered background knowledgecited by 9
- 2022A Unified Experiment Design Approach for Cyclic and Acyclic Causal Modelscited by 7
- 2023Efficient Enumeration of Markov Equivalent DAGscited by 6
- 2025Near-Optimal Experiment Design in Linear non-Gaussian Cyclic Modelscited by 4
- 2021Universal Lower Bound for Learning Causal DAGs with Atomic Interventionscited by 2
- 2025Characterization and Learning of Causal Graphs from Hard Interventionscited by 2
- 2023A Fixed-Parameter Tractable Algorithm for Counting Markov Equivalence Classes with the same Skeletoncited by 1
- 2025Less Greedy Equivalence Searchcited by 1
12 most cited of 14 All 14 (JSON)
- 2025Near-Optimal Experiment Design in Linear non-Gaussian Cyclic Models25 Sep 2025
- 2025Design of Experiment for Discovering Directed Mixed Graph2 Sep 2025
- 2025Less Greedy Equivalence Search27 Jun 2025
- 2025Characterization and Learning of Causal Graphs from Hard Interventions2 May 2025
- 2024Membership Testing in Markov Equivalence Classes via Independence Query Oracles9 Mar 2024
- 2023A Fixed-Parameter Tractable Algorithm for Counting Markov Equivalence Classes with the same Skeleton6 Oct 2023
- 2023Do we become wiser with time? On causal equivalence with tiered background knowledge2 Jun 2023
- 2023Active causal structure learning with advice31 May 2023
- 2023Efficient Enumeration of Markov Equivalent DAGs28 Jan 2023
- 2022Active Learning for Optimal Intervention Design in Causal Models10 Sep 2022
- 2022Causal Structure Learning: a Combinatorial Perspective2 Jun 2022
- 2022A Unified Experiment Design Approach for Cyclic and Acyclic Causal Models20 May 2022
12 newest of 14 All 14 (JSON)