Computation in Causal Graphs

Abstract

The goal of this paper is to introduce some of the important concepts in causal graph theory and examine them from combinatorial and computational perspectives. Of fundamental importance in applications of causal models that use graphs are dependence-separators or, simply, $d$-separators. A vertex set $Z$ is a $d$-separator for a pair of disjoint vertex sets $(X,Y)$ if $X$ and $Y$ are independent conditioned on $Z$. For the case of a single-setpair it is known that $d$-separators can be found efficiently by elegant network flow techniques. In this paper, we consider $d$-separators for a collection $\{(X_1,Y_1),(X_2,Y_2),\dots,(X_k,Y_k)\}$ of setpairs. We focus on two classes of combinatorial objects in this multiple-setpair framework: $d$-separators and $d$-super-separators. We say that $Z$ is a $d$-separator for multiple setpairs if, for each $i$, $X_i$ and $Y_i$ are independent conditioned on $Z$; we say that $Z$ is a $d$-super-separator if, for each $i$, there exists $Z_i\subseteq Z$, such that $X_i$ and $Y_i$ are independent conditioned on $Z_i$. For the latter object, we give an $O(\log^2k)$-approximation algorithm for the problem of finding a minimum cost $d$-super-separator. The focus on approximation algorithms is necessary as we show this problem is NP-complete. For the former object, we show it is hard to determine whether a $d$-separator exists, even when there are just five setpairs. This problem remains hard even if each setpair consists of singleton vertices, provided the number of setpairs is large. On the positive side, we show that if there are a fixed number of singleton setpairs then a $d$-separator for multiple setpairs can be found in polynomial time, if one exists.