Research map / Learning theory and algorithms / Combinatorial and search optimization
An Improved Clique-Picking Algorithm for Counting Markov Equivalent DAGs via Super Cliques Transfer
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.
Speeds up the Clique-Picking algorithm for counting Markov equivalent DAGs by transferring super cliques and super residuals across rooted clique trees, reducing UCCG generation cost from O(m(|V|+|E|)) to O(m^2).
Problem
Counting the number of Markov equivalent DAGs (MEC size) for a CPDAG is polynomial-time via Clique-Picking, but generating undirected connected components for every root clique is costly and repeated across recursive calls.
Approach
Introduces super cliques and super residuals within rooted clique trees and a super clique transfer operation that derives the UCCGs for a new root clique from those of its parent clique in the tree, avoiding recomputation from scratch.
Key results
- ICP is faster than CP across all tested settings; e.g., at |V|=4096 with r=0.34, average time 707.5s vs 1169.8s for CP.
- Runtime advantage grows with graph density: at |V|=2048, r=0.46 the Step-2 ratio TCP,2/TICP,2 reaches 264.5 on 1024-vertex graphs (vs 5.3 at r=0.04).
- Theoretical cost of computing UCCGs for all root cliques reduced from O(m(|V|+|E|)) to O(m^2).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Super Cliques Transfer for UCCG generation instead of the original CP generation procedure | Clique-Picking algorithm · Chordal graphs, |V|=512, r=0.34 | running time (seconds): 2.081 -> 1.022 | Helped |
| Use Super Cliques Transfer for UCCG generation instead of the original CP generation procedure | Clique-Picking algorithm · Chordal graphs, |V|=1024, r=0.34 | running time (seconds): 15.579 -> 8.048 | Helped |
| Use Super Cliques Transfer for UCCG generation instead of the original CP generation procedure | Clique-Picking algorithm · Chordal graphs, |V|=2048, r=0.34 | running time (seconds): 125.181 -> 68.048 | Helped |
| Use Super Cliques Transfer for UCCG generation instead of the original CP generation procedure | Clique-Picking algorithm · Chordal graphs, |V|=4096, r=0.34 | running time (seconds): 1169.811 -> 707.484 | Helped |
| Use Super Cliques Transfer for UCCG generation instead of the original CP generation procedure | Clique-Picking algorithm · Chordal graphs, |V|=512, r=0.08 | running time (seconds): 1.494 -> 0.842 | Helped |
| Use Super Cliques Transfer for UCCG generation instead of the original CP generation procedure | Clique-Picking algorithm · Chordal graphs, |V|=1024, r=0.08 | running time (seconds): 9.974 -> 5.586 | Helped |
| Use Super Cliques Transfer for UCCG generation instead of the original CP generation procedure | Clique-Picking algorithm · Chordal graphs, |V|=2048, r=0.08 | running time (seconds): 74.940 -> 40.545 | Helped |
| Use Super Cliques Transfer for UCCG generation instead of the original CP generation procedure | Clique-Picking algorithm · Chordal graphs, |V|=4096, r=0.08 | running time (seconds): 660.435 -> 387.491 | Helped |
| Use Super Cliques Transfer for UCCG generation instead of the original CP procedure | Clique-Picking Step 2 · Chordal graphs, |V|=1024, r=0.04 to 0.46 | Step 2 runtime ratio (CP/ICP): 5.34; 7.56; 18.43; 47.59; 153.55 | Helped |
| Use Super Cliques Transfer for UCCG generation | Clique-Picking Step 2 · Chordal graphs, |V|=2048, r=0.04 to 0.46 | Step 2 runtime ratio (CP/ICP): 12.27; 17.16; 39.70; 95.35; 264.54 | Helped |
Limitations
- Advantage depends on the number of cliques being substantially smaller than vertices and edges (small theta).
- Experiments limited to synthetic random chordal graphs implemented in Julia on a single-thread laptop.
Experimental setup
Datasets: randomly generated chordal graphs via minimal triangulation
Benchmarks: synthetic chordal graphs with varying vertex counts (512-4096) and densities
Metrics: average running time (seconds) runtime difference runtime ratio
Baselines: Clique-Picking (CP)
Builds on: Clique-Picking algorithm maximum cardinality search running intersection property
Closest papers by meaning
- A Fixed-Parameter Tractable Algorithm for Counting Markov Equivalence Classes with the Same Skeleton (AAAI 2024 · similarity 0.87)
- Interventional Causal Discovery in a Mixture of DAGs (NeurIPS 2024 · similarity 0.85)
- ProDAG: Projected Variational Inference for Directed Acyclic Graphs (NeurIPS 2025 · similarity 0.84)
- Relaxing partition admissibility in Cluster-DAGs: a causal calculus with arbitrary variable clustering (NeurIPS 2025 · similarity 0.84)
- Optimal Quasi-clique: Hardness, Equivalence with Densest-k-Subgraph, and Quasi-partitioned Community Mining (AAAI 2024 · similarity 0.84)
- A Fast Exact Solver with Theoretical Analysis for the Maximum Edge-Weighted Clique Problem (AAAI 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.