  We study the problem of learning the causal relationships between a set of
observed variables in the presence of latents, while minimizing the cost of
interventions on the observed variables. We assume access to an undirected
graph $G$ on the observed variables whose edges represent either all direct
causal relationships or, less restrictively, a superset of causal relationships
(identified, e.g., via conditional independence tests or a domain expert). Our
goal is to recover the directions of all causal or ancestral relations in $G$,
via a minimum cost set of interventions. It is known that constructing an exact
minimum cost intervention set for an arbitrary graph $G$ is NP-hard. We further
argue that, conditioned on the hardness of approximate graph coloring, no
polynomial time algorithm can achieve an approximation factor better than
$\Theta(\log n)$, where $n$ is the number of observed variables in $G$. To
overcome this limitation, we introduce a bi-criteria approximation goal that
lets us recover the directions of all but $\epsilon n^2$ edges in $G$, for some
specified error parameter $\epsilon > 0$. Under this relaxed goal, we give
polynomial time algorithms that achieve intervention cost within a small
constant factor of the optimal. Our algorithms combine work on efficient
intervention design and the design of low-cost separating set systems, with
ideas from the literature on graph property testing.
