Pearl's do calculus is a complete axiomatic approach to learn the
identifiable causal effects from observational data. When such an effect is not
identifiable, it is necessary to perform a collection of often costly
interventions in the system to learn the causal effect. In this work, we
consider the problem of designing the collection of interventions with the
minimum cost to identify the desired effect. First, we prove that this problem
is NP-hard, and subsequently propose an algorithm that can either find the
optimal solution or a logarithmic-factor approximation of it. This is done by
establishing a connection between our problem and the minimum hitting set
problem. Additionally, we propose several polynomial-time heuristic algorithms
to tackle the computational complexity of the problem. Although these
algorithms could potentially stumble on sub-optimal solutions, our simulations
show that they achieve small regrets on random graphs.

使用最少的干预设计来识别可辨识别的因果效应问题是 NP-hard 且与最小打击集问题有联系，提出了一个算法来找到最优解或其对数近似，同时提出了多项式时间的启发式算法来解决计算复杂性问题。