Cost-Optimal Learning of Causal Graphs

Understand

We consider the problem of learning a causal graph over a set of variables with interventions.

• We study the cost-optimal causal graph learning problem: For a given skeleton (undirected version of the causal graph), design the set of interventions with minimum total cost, that can uniquely identify any causal graph with the given skeleton.
• We show that this problem is solvable in polynomial time.
• Later, we consider the case when the number of interventions is limited.