Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00493
Computation in Causal Graphs
Vol. 23, no. 2, pp. 317-344, 2019. Regular paper.
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.
|
Submitted: October 2017.
Reviewed: February 2018.
Revised: April 2018.
Accepted: May 2018.
Final: April 2019.
Published: April 2019.
Communicated by
Giuseppe Liotta
|
Journal Supporters
|