Research map / Probabilistic and scientific modeling / Causal discovery

A Fixed-Parameter Tractable Algorithm for Counting Markov Equivalence Classes with the Same Skeleton

AAAI 2024 · Probabilistic and scientific modeling › Causal discovery · approach: Differentiable and score-based DAG learning

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives a fixed-parameter tractable algorithm that counts Markov equivalence classes (MECs) sharing a given skeleton, parameterized by treewidth and maximum degree, via a "shadow" local representation of long-range MEC constraints and a tree-decomposition recursion.

Problem

Counting the number of Markov equivalence classes (MECs) of causal DAGs that have a given undirected skeleton G; no polynomial algorithm was known for general graphs.

Approach

Introduces the "shadow" of an MEC on a vertex subset: a partial MEC on the induced subgraph plus bits recording triangle-free path reachability between edges and vertices. Shadows summarize long-range v-structure/orientation constraints locally, so counts can be combined along a tree decomposition recursively.

Key results

• Gives an algorithm counting MECs of a graph with n nodes, treewidth k and max degree δ in O(n(2^{O(k^4 δ^4)} + n^2)) time.
• Runtime is polynomial when treewidth and maximum degree are bounded by constants, e.g. bounded-degree trees.

Limitations

• Exact polynomial-time complexity for general graphs remains open; the result is only FPT in treewidth and degree.
• Runtime is exponential in treewidth and degree, making it impractical for dense or high-treewidth graphs.

Experimental setup

Metrics: worst-case runtime complexity

Baselines: brute-force enumeration of DAGs with skeleton G

Builds on: Meek's rules Verma-Pearl characterization of Markov equivalence Andersson et al. chain graph characterization of MECs Ganian et al. FPT counting of MECs

Closest papers by meaning

• Coarsening Linear Non-Gaussian Causal Models with Cycles (NeurIPS 2026 · similarity 0.88)
• An Improved Clique-Picking Algorithm for Counting Markov Equivalent DAGs via Super Cliques Transfer (ICML 2025 · similarity 0.87)
• Sample Efficient Bayesian Learning of Causal Graphs from Interventions (NeurIPS 2024 · similarity 0.87)
• Markov Equivalence and Consistency in Differentiable Structure Learning (NeurIPS 2024 · similarity 0.87)
• Relaxing partition admissibility in Cluster-DAGs: a causal calculus with arbitrary variable clustering (NeurIPS 2025 · similarity 0.87)
• Interventional Causal Discovery in a Mixture of DAGs (NeurIPS 2024 · similarity 0.86)