Where Causal Experiment Planning Can and Cannot Be Shrunk

Choosing which variables to intervene on is the expensive part of causal discovery. Observational data leaves many causal arrows ambiguous, because several causal graphs explain the same data equally well. Settling those arrows, or making a target causal effect computable at all when hidden confounders are present, takes experiments, and picking the cheapest set of experiments is NP-hard. In practice people handle NP-hard problems by first running fast simplification rules that shrink a large instance down to a small hard core, then spending exponential time only on that core. This proposal asks, with proofs, when such shrinking is possible for causal experiment planning and when it cannot work.

The claim is a split. First, the ambiguity that comes from observational equivalence on its own is easy to compress. Under standard assumptions, planning a fixed batch of single-variable experiments that is guaranteed to orient every ambiguous arrow reduces to minimum vertex cover, so it inherits a linear-size shrinking procedure. Second, as soon as hidden confounders enter and the goal becomes making an effect identifiable, the problem behaves like directed graph separation. Separation problems provably cannot be shrunk to polynomial size unless a standard complexity assumption fails. If both halves hold, they tell algorithm designers which simplification rules are worth looking for and which are mathematically impossible. They also explain an apparent contradiction in the literature about whether dense graphs make experiment design harder or easier.

Background in plain terms

The first direction is kernelization. A kernel is a polynomial-time procedure that shrinks an instance with parameter $k$ (here, the experiment budget) to an equivalent instance whose size depends only on $k$. When that size is polynomial in $k$, the kernel is called polynomial. Lower bounds against polynomial kernels come from compositions: one packs many independent hard instances into a single instance whose parameter stays small. If a polynomial kernel existed, it would compress many independent bits into fewer bits, which would imply NP ⊆ coNP/poly. Two papers supply the tools and targets we reuse. Clique cover and graph separation: New incompressibility results proves that Directed Vertex/Edge Multiway Cut has no polynomial kernel in the cut size, even with only two terminals, and that the same holds for Multicut. Limits of Preprocessing carries such lower bounds into AI, including Bayesian-network inference parameterized by loop cutset. That paper studies inference in a known network, though. It does not study planning experiments to learn or identify structure, which is our problem.

The second direction is Markov equivalence class (MEC) ambiguity. An MEC is the set of causal graphs indistinguishable from observational data. It is summarized by a partially directed graph whose undirected parts, called chain components, are chordal. Chordal graphs have no long cycles without shortcuts and decompose into trees of cliques. Three lines of work plan experiments to remove this ambiguity: randomized designs, adaptive multi-round designs on clique trees, and greedy multi-variable designs, discussed below. A separate line handles hidden confounders. There, the obstacles to identifying an effect are subgraphs called hedges, and the cheapest set of interventions that breaks them all is a weighted hitting-set problem (Minimum Cost Intervention Design for Causal Effect Identification). A related problem, finding the fewest joint experiments that identify all learnable effects, reduces to coloring a conflict graph (Minimum Intervention Cover of a Causal Graph). Neither paper analyzes preprocessing.

The closest existing connection is Revisiting Causal Discovery from a Complexity-Theoretic Perspective. It gives a fixed-parameter algorithm for observational skeleton discovery, parameterized by edge-cut size in a given super-structure, and shows that the PC algorithm can be forced to test exponentially large conditioning sets. That paper motivates the view that cut structure governs tractability. It is still about observational testing with an FPT algorithm. It proves no kernel lower bound and does not touch interventions or the resolution of MEC ambiguity, which is where this proposal works.

Core Claim

Part A (the compressible side). Assume causal sufficiency (no hidden confounders) and faithfulness, and consider a non-adaptive batch of single-variable interventions that must orient every edge for every graph in the MEC. The minimum-cost such batch is exactly a minimum-weight vertex cover of the union of the chain components.

The argument we will make rigorous has two steps. For every undirected edge $u - v$ in a chordal chain component, some graph in the MEC makes $u \to v$ a "covered" edge, meaning $u$ and $v$ have the same parents apart from $u$ itself. Such a graph can be built from an elimination ordering that starts at $u$ and then $v$. A covered edge can only be oriented by intervening on one of its endpoints. Conversely, intervening on every vertex of a cover orients every edge directly.

Part A therefore inherits the classical $2k$-vertex kernel for vertex cover, together with its weighted versions. The consequence is that kernel lower bounds cannot come from observational ambiguity alone. This is deliberately a modest result. It is a sanity anchor, and it is also a strong baseline: it tells us which instances are trivial.

Part B (the incompressible side). Consider minimum-cost hedge breaking: choose interventions of total size at most $k$ such that a target effect $P(Y \mid do(X))$ becomes identifiable in a graph with hidden confounders. Parameterized by $k$, we conjecture this problem has no polynomial kernel unless NP ⊆ coNP/poly. The proof route is a polynomial parameter transformation from two-terminal Directed Vertex Multiway Cut. That source problem is known to be incompressible (Clique cover and graph separation). The transformation would encode each directed path from source to sink as a hedge inside a single confounded component, so that hitting all hedges equals cutting all paths.

The Minimum Cost paper's own heuristics are built on max-flow/min-cut, which hints at this cut structure. Its Singleton result also tells us where the construction has to live. If the target variables form one confounded component, the optimum is one intervention set. Across separate components, costs add up, which makes them a poor vehicle for OR-composition. So the hardness must be built inside one component.

Part C (where compression comes back). Hedge breaking should admit a polynomial kernel when parameterized jointly by budget $k$ and maximum hedge size $d$. In that regime it is a $d$-hitting set, and the standard sunflower-based reduction applies, giving $O(k^d)$ hedges. Bounded in-degree and small confounded components, the tractable regime noted in Minimum Intervention Cover, should imply bounded $d$.

Parts A through C together resolve the density tension recorded in the literature:

  • Sufficient setting. Dense cliques are the worst case for counting experiments (Randomized Experimental Design for Causal Graph Discovery). They are nonetheless trivially compressible, because a large clique simply forces a large cover.
  • Confounded setting. Dense graphs make hedge breaking easier because many variables are forced into the intervention set, as the Minimum Cost paper observes. The incompressibility comes from long, sparse, path-like confounded structure, not from density.

Research Program

Theory. The first theoretical task is to prove Part A carefully, including the weighted case and an extension to batches of interventions of size $q$. For the batched version we expect a reduction to a covering problem that still has a polynomial kernel in $k$ and $q$. We will flag clearly whether that holds.

The second task is the transformation behind Part B. The risky step is ensuring that the gadget creates no spurious hedges. If the direct transformation fails, the fallback is an OR-cross-composition. It would glue $t$ instances of an NP-hard hedge problem along a shared confounded spine, using about $\log t$ selector variables, so that breaking all hedges within budget is possible exactly when some instance is a yes-instance.

The third task is Part C. Beyond it, we will pose and attack one sharper question. Does hedge breaking admit a polynomial Turing kernel, that is, an adaptive procedure that solves the problem by asking polynomially many questions about poly($k$)-size subinstances? This is the formal counterpart of multi-round adaptive experimentation studied in Adaptivity Complexity for Causal Graph Discovery. That paper gives approximation guarantees for adaptive design and never asks about compression.

Engineering. We will implement the reduction rules as a preprocessing layer in front of the exact lazy hitting-set solver from Minimum Cost Intervention Design. The rules are vertex-cover crown and degree rules for Part A, and sunflower and dominance rules on hedges for Part C. The code will be built on graph classes from causal-learn and causality-lab. We will also generate the hard instance families produced by the Part B construction, so that the theory can be checked against reality.

Baselines

Raw exact solver (do-nothing reference). The exact lazy minimal-hedge hitting-set solver of Minimum Cost Intervention Design, run on unreduced instances. It answers the obvious question: does preprocessing buy anything? It is run on identical instances, with the same time limit per instance, the same machine, and the same hitting-set backend. Beating it means a lower median time to an exact solution and more instances solved within the limit. Kernel time is counted in our runtime.

Min-cut and greedy heuristics (strongest practical competitor). The polynomial-time max-flow/min-cut and greedy-shrinkage heuristics from the same paper. They are the strongest competitor because they are what practitioners would actually run. On Lacuna the paper reports only that these run in "fractions of a second" on graphs up to 200 nodes and achieve "very low normalized regret (often near zero)". No exact regret value was found. We will regenerate their numbers on our instances. Our method beats them if it returns certified optima within a comparable time budget on the instances where their regret is nonzero. Our lower-bound families are designed to make that regret visible.

Greedy submodular design (sufficient setting). Near-Optimal Multi-Perturbation Experimental Design for Causal Structure Learning proposes the Double Greedy Continuous and Separating System Greedy methods, which pick experiments greedily by sampling graphs from the MEC. No exact numeric result was found on Lacuna for either method on random graphs or the DREAM3 yeast network. We compare cost and wall-clock time under equal time budgets, using their 40-node random graphs and DREAM3.

Randomized design (sufficient setting). Randomized Experimental Design chooses interventions at random. It reports that the largest remaining undirected clique "typically hovers around two or three" even at $n = 15{,}000$ after one or two interventions. This is relevant because it suggests most sufficient-setting instances are nearly trivial anyway.

Ablation. To isolate the key ingredient, we run the Part C sunflower and dominance rules alone, without the vertex-cover rules. This separates gains due to hedge structure from gains due to generic cover structure.

Why not just…?

Why not just run greedy or min-cut heuristics and skip exact methods? Their regret on standard benchmarks may well be near zero, as reported, and in that case exactness looks unnecessary. The open question is whether that holds outside the benchmarks. The Part B construction gives a principled family of path-heavy confounded instances on which cut-based heuristics should be stressed. Measuring their regret there against certified optima settles whether near-zero regret reflects the problem or the benchmark. If regret stays near zero on these families too, we will report that the practical case for exact solving is weak.

Why not just use randomized design, since it already makes the sufficient case cheap? This is a real threat in the causally sufficient setting, and Part A concedes it: that regime collapses to vertex cover and is easy. Randomized design does not address non-uniform costs. It also offers nothing once hidden confounders require specific joint interventions for identification, as both Minimum Cost and Minimum Intervention Cover show. For that reason the main contribution sits in the confounded regime.

Why not stop at NP-hardness? NP-hardness does not separate vertex cover, which has a $2k$ kernel, from multiway cut, which has none. Part A and Part B are two NP-hard problems that fall on opposite sides of that line. The lower bound tells designers to stop searching for single-instance shrinking rules for hedge breaking. Instead they should pursue the bounded-hedge-size parameterization or the Turing kernel. That is guidance NP-hardness cannot give.

Why not just design an FPT algorithm, as was done for PC with edge cuts? An FPT algorithm alone, in the style of Revisiting Causal Discovery, still processes the whole graph. Kernels matter because the reduced core can be handed to any off-the-shelf exact solver. Part B is exactly the statement that, for hedge breaking, this handoff cannot be polynomial-size in general. We will still report an FPT running time wherever our proofs give one.

Proposed Experiments

Benchmarks. We use Barley, Water, and Mehra with synthetic hidden confounders, following Minimum Cost Intervention Design. We add Erdős–Rényi graphs up to 200 nodes with varying density and confounder rate, plus DREAM3 and random 40-node graphs for the sufficient setting. Metrics are:

  • kernel size, both remaining variables and remaining hedges, as functions of $n$ and of the optimum $k$;
  • time to an exact solution and fraction of instances solved within the limit;
  • heuristic regret against certified optima.

First decisive check (Part A). On sufficient instances, the optimal batch from any exact search must coincide in cost with the minimum-weight vertex cover of the chain components. Any counterexample falsifies Part A and would be reported as such.

Second decisive check (Parts B and C). Kernel size should behave differently on the two kinds of instances.

Instance type Predicted kernel size
Bounded-hedge-size instances Grows like $k^d$ and is independent of $n$
Lower-bound families Grows with $n$ even at fixed $k$

If the rules shrink the lower-bound families to poly($k$) size anyway, either the construction or the conjecture is wrong. That outcome would point toward a polynomial kernel instead.

Third check (density tension). Plot kernel size against edge density separately for sufficient and confounded instances. The prediction is that density helps compression in both settings, and that hardness tracks long confounded paths rather than density.