optimal passive experiment design for full identification of causal structure learning

Directed acyclic graphs stand as one of the prevailing approaches for representing causal relationships within a set of variables. with observational or interventional data, certain undirected edges within a causal dag can be oriented. performing intervention can be done in two different settings, passive and active. here, we prove that an optimal intervention set can be obtained based on the minimum vertex cover of a graph. we propose an algorithm that efficiently identifies such an optimal intervention set for chordal graphs within polynomial time. performing intervention on this optimal set recovers all the undirected edges in graph g, regardless of the underlying ground truth dag. furthermore, we present an algorithm for evaluating the performance of passive algorithms. this evaluation provides insights into how many intervention steps of a specific algorithm are required to recover all edges in the causal graph for any possible underlying ground truth in the equivalence class. experimental findings underscore that the number of nodes in the optimal intervention set increases with growing the number of nodes in a graph, where the edge density is fixed, and also increases with the rising edge density in a graph with a fixed number of nodes.