Confounder selection, namely choosing a set of covariates to control
for confounding between a treatment and an outcome, is arguably the
most important step in the design of observational studies. Previous
methods, such as Pearl's celebrated back-door criterion, typically
require pre-specifying a causal graph, which can often be difficult in
practice. We propose an interactive procedure for confounder selection
that does not require pre-specifying the graph or the set of observed
variables. This procedure iteratively expands the causal graph by
finding what we call “primary adjustment sets” for a pair of
possibly confounded variables. This can be viewed as inverting a
sequence of latent projections of the underlying causal
graph. Structural information in the form of primary adjustment sets
is elicited from the user, bit by bit, until either a set of
covariates are found to control for confounding or it can be
determined that no such set exists. We show that if the user correctly
specifies the primary adjustment sets in every step, our procedure is
both sound and complete.

§ INTRODUCTION

Consider an observational study where the causal effect of a treatment
variable $X$ on an outcome variable $Y$ is of interest. Arguably,
the single most widely used strategy for identifying the causal effect
is through confounder adjustment, which employs a set of observed
covariates that are carefully chosen to control for confounding. Let
$Y(x)$ be the potential outcome of $Y$ had the treatment $X$ been
intervened on and set to level $x$. A set of covariates $S$ control
for confounding if for every observed level $x$ of $X$, $X$ and $Y(x)$
are independent within each stratum defined by $S$, a condition known
as conditional ignorability or conditional exchangeability
[Rosenbaum and Rubin, 1983, Greenland and Robins, 2009, Hernán and Robins, 2020]. The
task of choosing such a set of covariates is called confounder

While there exist a variety of approaches and criteria for confounder
selection (see Guo et al., 2022 for a recent survey), it is
clear that this cannot be answered by data alone and hence is
fundamentally different from statistical variable selection (e.g. stepwise algorithms in linear regression). That is,
domain knowledge about the underlying causal mechanism or structure is
indispensable. Causal
graphical model provides an intuitive framework for formalizing such
knowledge. Specifically, if we have available a causal directed
acyclic graph (DAG) model for relevant variables in an observational
study, the celebrated back-door criterion [Pearl, 1993]
answers whether or not a set of covariates $S$ controls for confounding, and this criterion is
complete in a sense that will be described in <ref>. The set $S$ is called a sufficient adjustment set if it satisfies the back-door criterion.
When there are more than one sufficient adjustment
sets, one may wish to further choose a set based on size or
statistical efficiency <cit.>. Yet,
these are secondary objectives that we will set aside for the rest of this
paper. As far as validity is concerned, confounder selection is sometimes
considered a “solved problem” in light of the back-door
criterion, provided that a causal DAG (or a latent projection of
the DAG) can be pre-specified to represent our domain knowledge and

However, the back-door criterion is often difficult to apply in
practice. As the back-door criterion is a global condition about
the candidate set of covariates $S$, the treatment $X$, the outcome
$Y$ and other
variables in the system (see <ref> for
its statement), a practitioner must be able to (1) conceive
all the variables, observed or unobserved, that are relevant, (2)
posit all causal relations among these variables, (3) understand how a
DAG encodes causal assumptions, and (4) draw
the DAG accordingly, or at least a large portion of it, to transcribe
the posited relations graphically. While tools and protocols for drawing DAGs
have been developed [Shrier and Platt, 2008, Haber et al., 2022], this
is still a formidable process in practice. It is often difficult to
conceive all the relevant variables, let alone posit all causal
relations among them.

§.§ Overview of the iterative graph expansion procedure

In this paper, we take an interactive, bottom-up approach to
confounder selection that does
not require pre-specifying the causal graph. Our method, called
iterative graph expansion, is
based on a symmetric reformulation of Pearl's back-door criterion and
can be viewed as the inverse of the well-known latent projection
[Verma and Pearl, 1990]. The knowledge about the underlying
causal graph is elicited from the user, bit by bit, until one or more
sets of covariates that meet the symmetric back-door criterion are found,
or it is determined that so such set exists. For this procedure, a key new concept is a
primary adjustment set: an adjustment set for a pair of variables is called primary
if for every common ancestor of the two variables, at least one of the
two causal paths from the ancestor to these two variables are blocked
by the adjustment set. Intuitively, a primary adjustment set removes
all “immediate” confounding between the two variables.

More specifically, the process of graph expansion starts with a working
graph consisting of two vertices — the treatment $X$ and the outcome $Y$ — and a dashed
bidirected edge, representing possible uncontrolled
confounding, between them. In each step, the user is asked to provide
candidates of primary adjustment sets to expand a dashed
bidirected edge selected from the current working graph; if no such set exists,
the dashed bidirected edge is changed to a solid edge. If primary
adjustment sets do exist, then every such set leads to an expanded graph:
the selected dashed edge is removed and those vertices in the primary
adjustment set are introduced to the graph, with
a dashed bidirected edge drawn between every new vertex and every old
vertex, as well as between every pair of new vertices.
This process is repeated until the treatment and the outcome are no longer
connected by solid or dashed bidirected edges. When this occurs, variables other than $X$
and $Y$ in the working graph form a sufficient adjustment set.

rv/.style=circle,inner sep=1pt,draw,font=,
lv/.style=circle,inner sep=1pt,fill=gray!20,draw,font=,
fv/.style=rectangle,inner sep=1.5pt,fill=gray!20,draw,font=,
node distance=15mm, >=stealth
[rv] (X) $X$;
[rv, above right of=X] (B) $B$;
[rv, below right of=B] (Y) $Y$;
[rv, above left of=B] (D) $C$;
[rv, above right of=B] (C) $D$;
[->, thick] (B) – (X);
[->, thick] (B) – (Y);
[->, thick] (D) – (B);
[->, thick] (D) – (X);
[->, thick] (C) – (B);
[->, thick] (C) – (Y);

rv/.style=circle,inner sep=1pt,draw,font=,
node distance=15mm, >=stealth
[rv] (X) $X$;
[rv, right of=X, xshift=0.5cm] (Y) $Y$;
[<->, dashed, thick, color=red] (X) – (Y);

rv/.style=circle,inner sep=1pt,draw,font=,
lv/.style=circle,inner sep=1pt,fill=gray!20,draw,font=,
fv/.style=rectangle,inner sep=1.5pt,fill=gray!20,draw,font=,
node distance=15mm, >=stealth
[rv] (X) $X$;
[rv, above right of=X] (B) $B$;
[rv, below right of=B] (Y) $Y$;
[<->, thick, dashed, red] (B) – (X);
[<->, thick, dashed] (B) – (Y);

rv/.style=circle,inner sep=1pt,draw,font=,
lv/.style=circle,inner sep=1pt,fill=gray!20,draw,font=,
fv/.style=rectangle,inner sep=1.5pt,fill=gray!20,draw,font=,
node distance=15mm, >=stealth
[rv] (X) $X$;
[rv, above right of=X] (B) $B$;
[rv, below right of=B] (Y) $Y$;
[rv, above left of=B] (D) $C$;
[<->, thick, dashed] (B) – (Y);
[<->, thick, dashed] (D) – (B);
[<->, thick, dashed, red] (D) – (X);
[<->, thick, dashed, bend left] (D) to (Y);

rv/.style=circle,inner sep=1pt,draw,font=,
lv/.style=circle,inner sep=1pt,fill=gray!20,draw,font=,
fv/.style=rectangle,inner sep=1.5pt,fill=gray!20,draw,font=,
node distance=15mm, >=stealth

[rv] (X) $X$;
[rv, above right of=X] (B) $B$;
[rv, below right of=B] (Y) $Y$;
[rv, above left of=B] (D) $C$;
[<->, thick, dashed] (B) – (Y);
[<->, thick, dashed] (D) – (B);
[<->, thick, dashed, out = 0, bend left] (D) to (Y);

An illustration of the iterative graph expansion using
the “butterfly bias” example. The edge chosen for expansion is highlighted in red.

<Ref> illustrates the iterative graph
expansion when the underlying causal graph is a “butterfly” (the leftmost
graph). In the first iteration, the algorithm expands the potential
bidirected edge $X \dbarrow Y$ with primary adjustment set $\{B\}$.
This creates two more potential bidirected edges, $B
\dbarrow X$ and $B \dbarrow Y$. The second iteration of the algorithm
expands $B \dbarrow X$ by further adding $\{C\}$ to the
graph, which creates three more potential bidirected edges,
$C \dbarrow X$, $C \dbarrow Y$, and $C \dbarrow B$. The next iteration
simply removes $C \dbarrow X$, as there is no
confounding between $C$ and $X$. This leads to the rightmost graph,
where $X$ and $Y$ are not connected by bidirected edges. Hence, the algorithm
returns $\{B,C\}$ as a sufficient adjustment set.
Similarly, the set $\{B,D\}$ can also be identified as a sufficient
adjustment set through another sequence of expansions.
In fact, $\{B,C\}$ and $\{B,D\}$ are the only two minimal sufficient
adjustment sets in this example. More examples are given in
<Ref> and <Ref>.

Compared to existing methods for confounder selection, such as directly
applying the back-door criterion, the iterative graph expansion
procedure has several advantages.
First of all, it makes structural queries “economical” in the sense
that only so much
information needed for confounder selection is elicited from the user.
All other information, including the orientation of directed edges among
variables in the working graph, is never requested.
Second, familiarity with causal graphs (such
as how to apply d-separation) is not required to deploy the procedure;
the user is only expected to identify common causes and mediators.
Finally, we show that this procedure is sound and complete in the
following sense: if all the primary adjustment
sets specified by the user are indeed primary, then every
adjustment set identified by the procedure is sufficient; further, if
the user correctly specifies all the minimal primary adjustment sets
in each step, then every minimal sufficient adjustment set will be
identified by the procedure.

It is worth mentioning that there are other proposals in the
literature for confounder selection that only require partial
knowledge about the causal graph, including, notably, the disjunctive
cause criterion due to VanderWeele and Shpitser, 2011; see also
VanderWeele, 2019 for its variants. The disjunctive
cause criterion selects all the observed pre-treatment covariates that
are ancestors (i.e. direct or indirect causes) of the treatment, the
outcome or both. VanderWeele and Shpitser, 2011 showed that this
adjustment set is sufficient whenever the set of observed
pre-treatment covariates contains any sufficient adjustment set as a
subset; see also Richardson et al., 2018, Guo et al., 2022. While
this criterion can be useful when data has already been collected and domain
knowledge is scarce, verifying the assumption that the set of
collected covariates contains a sufficient adjustment set can be as
difficult as the task of confounder selection itself.
Moreover, the disjunctive cause criterion and many other
existing proposals require pre-specifying the set of observed
covariates. As such, they are not best suited for designing an
observational study, when a primary goal is to determine how data
should be collected. Finally, to the best of our knowledge, all the
existing methods for confounder selection are “static” — they
cannot learn from the user in an interactive way.

§.§ Other contributions and organization of this paper

The iterative graph expansion procedure is built on several
conceptual and technical novelties, summarized as follows.

First, we provide a definition of confounding paths,
the symmetric structure that induces confounding between two
variables. Specifically, a path between $A$ to $B$ is called
confounding if it has two endpoint arrowheads. This allows us
to symmetrize Pearl's back-door criterion
and reduce the task of confounder selection to blocking all confounding paths
between the treatment and the outcome.
The notion of a confounding path complements earlier efforts in
the literature towards properly defining a confounder, or more
precisely, a confounding
variable. VanderWeele and Shpitser, 2013 reviewed
several popular notions of confounders and showed that none
of them is satisfactory. They further provided an alternative
definition: a confounder is a pre-exposure
covariate $C$ for which there exists a set of other covariates $S$
such that $(S,C)$ is a sufficient adjustment set but no proper subset
of $(S,C)$ is sufficient. However, this definition does not lead to a practical
procedure for selecting confounders.

Second, we adopt the notion of confounding arcs from <cit.> and provide a concrete definition: a confounding arc
is a confounding path with no colliders.
It is easy to see that every a confounding path can be
decomposed into one or more confounding arcs. Importantly, when a set
of covariates block a confounding arc, all its superset also blocks
the same arc; the same property doesn't hold for confounding
paths consisting of more than one confounding arcs. Nevertheless, we
show that, by iteratively blocking confounding arcs, we can eventually
block all the confounding paths between the treatment and the outcome.

Third, we introduce a district criterion for confounder
selection, which posits that a set $S$ is an adjustment set if $X$ and
$Y$ are in different “districts” in the latent projection graph over $S \cup
\{X,Y\}$. This is equivalent to the symmetric back-door criterion but
can be easier to check in practice.

Finally, to develop our procedure and prove its soundness and
completeness, we introduce a set of refined m-connection/separation
relations, along with a set of notation, to reason about confounding
paths and arcs. As with the usual m-connection, we show that these
relations are preserved by latent projection.

The rest of this paper is organized as follows. In
<ref>, we introduce the preliminaries on
causal graphical models, including some basic graphical terms,
m-separation and latent projection. In <ref>,
we introduce
confounding paths, confounding arcs and refined m-connection,
with which we formulate a symmetric version of the back-door criterion. We study the
properties of refined m-connection in <ref>. We show that latent
projection preserves refined m-connection (<ref>), which
then leads to the district criterion
(<ref>). Graphoid-like properties of
refined m-connection are also studied in <ref>. We present iterative our
graph expansion procedure in <ref>. When the user acts
like an oracle and answers all queries about primary adjustment sets
correctly, our procedure is
shown to be both sound and complete (<ref>). Practical
considerations and subroutines needed for the procedure are studied
in <ref>. We conclude with
some discussion in <ref>. Technical proofs and other
supplementary materials can be found in the appendix.

§ PRELIMINARIES OF CAUSAL GRAPHICAL MODELS

§.§ Basic graphical concepts

A directed mixed graph $\gG = (\sV, \sD, \sB)$ is a graph over a finite
vertex set $\sV$ that consists of two types of edges, directed edges $\sD
\subseteq \sV \times \sV$ and bidirected edges $\sB \subseteq \sV
\times \sV$. Each vertex in $\sV$ represents a random variable.
We write $A \rightarrow B$ for a directed edge $(A,B) \in \sD$, which signifies
the presence of a direct causal effect of $A$ on $B$; by “direct”, we mean
this causal effect is not mediated by other variables in the graph.
We write $A \leftrightarrow B$ for a bidirected edge $(A,B) \in \sB$ (and hence
also $(B,A) \in \sB$), which signifies the presence of
endogeneity — a form of unmeasured confounding — between
$A$ and $B$; endogeneity introduces non-causal association that cannot
be explained away by other variables in the graph.
A maximal set of vertices connected by bidirected edges is called a district.
Between two vertices $A,B \in \sV$, we allow the existence of both a directed edge and a bidirected edge.
A directed cycle is a sequence of directed edges $v_1 \rightarrow \dots \rightarrow v_l \rightarrow v_1$ with $v_l = v_1$ and $l > 1$.
If $\gG$ contains no directed cycle, we call $\gG$ an acyclic directed mixed graph (ADMG).
Further, if $\gG$ contains no bidirected edge, we call it a directed acyclic graph (DAG).

A walk is a sequence of adjacent edges of any type or orientation.
If all vertices on a walk are distinct, we say it is a path.
For ADMGs, it is necessary
to specify a walk or path as a sequence of edges instead of vertices, as
there may exist both directed and bidirected edges between two
vertices. A walk or path is directed if it is formed of directed edges
pointing in the same direction.

For any walk $\pi$, a non-endpoint vertex $A$ is said to be a
collider on $\pi$ if both the edges before and after $A$ have
an arrowhead pointing to $A$, or in other words, if $\pi$ contains
$\rightarrow A \leftarrow$, $\rightarrow A \leftrightarrow$,
$\leftrightarrow A \leftarrow$ or $\leftrightarrow A
\leftrightarrow$.
Note that a vertex can be a collider on one path and a non-collider on another path.
We call a walk or path without colliders an arc and denote it by
a squiggly line ($\nosquigno$); the same concept (with some slight
variation) is also referred to as a trek by some authors
[Spirtes et al., 1993, Sullivant et al., 2010].
An arc can be further specified by the arrowhead or tail added
to the squiggly line.
A directed path from $A$ to $B$ is
written as $A \rightdirpath B$ or $B \leftdirpath A$. A path from $A$ to $B$ with no
colliders and two endpoint arrowheads is called a confounding arc
and written as $A \confarc B$. We use a half-arrowhead to indicate that the
endpoint can be either an arrowhead or a tail. For example, $A \halfsquigfull B$
means is the path is either $A \rightdirpath B$ or $A \confarc B$.

We adopt the common familial terminologies for graphical models. A
vertex $A$ is said to be a parent of another vertex $B$ and
$B$ a child of $A$ in the
ADMG $\gG$ if $\gG$ contains $A \rightarrow B$; and $A$ is said to be
an ancestor of $B$ and $B$ a descendant of $A$ if $\gG$
contains $A \rightsquigarrow B$.
(This differs from the convention
that $A$ is considered both an ancestor and a descendant of itself used by
many authors.)
With these relations, we define sets $\pa_{\gG}(v), \ch_{\gG}(v),
\an_{\gG}(v), \de_{\gG}(v)$ for a vertex $v \in \sV$ and extend these
definitions to a vertex set $A \subseteq \sV$ disjunctively, e.g.,
$\pa_{\gG}(A) := \cup_{v \in A} \pa_{\gG}(v)$, $ \ch_{\gG}(A) :=
\cup_{v \in A} \ch_{\gG}(v)$, etc. Additionally, we let
$\overline{\an}_{\gG}(A) := \an(A) \cup A$. The subscript $\gG$ is often
omitted when it is clear from the context.

§.§ m-separation

Introduced by Richardson, 2003,
m-separation extends the d-separation criterion
for conditional independence in DAGs
[Pearl, 1988] to ADMGs. Given an ADMG $\gG$, a path is said to be m-connected
given $C \subseteq \sV$ if every non-collider on the path is not in
$C$, and every collider on the path is in $C$ or has a descendant in
$C$. For disjoint $A,B,C \subseteq \sV$, if there exists a
m-connected path in $\gG$ from any vertex in $A$ to any
vertex in $B$ given $C$, we say $A$ and $B$ are m-connected in $\gG$
given $C$ and denote it as $A \mconn B \mid C\;[\gG]$; otherwise, we say they
are m-separated by $C$ in $\gG$ and denote it as $A \msep B
\mid C\;[\gG]$. Instead of using the common notation, $A \not\indep B
\mid C\;[\gG]$ and $A \indep B \mid C\;[\gG]$ respectively, for the
same purpose, in this paper
we opt for a set of notation that more clearly describes the type of the underlying path:
(1) the half-arrowheads indicate that both endpoints are unrestricted in terms of arrowhead
or tail; (2) the wildcard character `$\ast$' means the path can have zero,
one or several colliders. Thus, $A \mconn B$ refers to all paths
from $A$ to $B$. The advantages of this set of notation will become clearer in

§.§ Latent projection

In many cases, a graph can contain variables that are not observed (or
observable[We say a variable is observed if the
variable has been measured and recorded, and we say a variable is
observable if the variable can be measured. Typically, the
former notion is used when analyzing a study and the latter when
designing a study. For convenience, we do not differentiate the two
and use “observed” throughout. ]) and it is convenient to
contemplate the latent projection of the graph onto the set of
observed variables [Pearl and Verma, 1991].
Let $\gG = (\sV,\sD,\sB)$ be an ADMG and let $\sV =\tilde{\sV} \cup \sU$ be a
partition (so $\tilde{\sV} \cap \sU = \emptyset$).
The latent projection of $\gG$ onto $\tilde{\sV}$, written as $\tilde{\gG}
= \gG(\tilde{\sV})$, is defined as the ADMG $\tilde{\gG} =
(\tilde{\sV}, \tilde{\sD}, \tilde{\sB})$ with directed and bidirected edges given by

* $A \rightarrow B$ in $\tilde{\gG}$ if there exists a directed path in $\gG$ on which all the non-endpoint vertices are in $\sU$ (such paths are denoted as $A
\overset{\text{via}\,\sU}{\rightsquigarrow} B$), and

* $A \leftrightarrow B$ in $\tilde{\gG}$ if there exists a path
from $A$ to $B$ such that the path has two endpoint arrowheads and no
colliders and has all the non-endpoint vertices in $\sU$ (such paths
are denoted as $A  \overset{\text{via}\,\sU}{\leftrightsquigarrow} B$).

Trivially, $A \rightarrow B$ in $\gG$ implies $A \rightarrow B$ in $\tilde{\gG}$ and $A \leftrightarrow B$ in $\gG$ implies $A \leftrightarrow B$ in $\tilde{\gG}$.
Using the squiggly line notation, latent projection can be compactly stated as

\[
\begin{Bmatrix}
\rightarrow \\
\leftarrow \\
\leftrightarrow \\
\end{Bmatrix}
\quad
\iff
\quad
\begin{Bmatrix}
\overset{\text{via}\,\sU}{\rightdirpath} \\
\overset{\text{via}\,\sU}{\leftdirpath} \\
\overset{\text{via}\,\sU}{\fullsquigfull} \\
\end{Bmatrix}
\]

By construction, latent projection preserves
acyclicity. It is well-known that the m-separation is
preserved by latent projection [Verma and Pearl, 1990, Evans, 2018]: for disjoint $A, B, C \subset
\tilde{\sV}$,

\[
A \msep B \mid C\;[\gG(\tilde{\sV})] \quad \iff \quad A \msep B
\mid C\;[\gG].
\]

In <ref>, we strengthen this result by showing that latent projection preserves refined forms of m-separation.

A central problem in causal inference is to identify the causal
effect of a treatment variable $X$ on an outcome variable $Y$ under the causal model[In this paper, we take the causal model to be the finest fully randomized causally interpretable structured tree graph (FFRCISTG) model associated with graph $\gG_{\text{full}}$, the underlying DAG whose latent projection is the graph $\gG$. The FFRCISTG model makes weaker assumptions than the non-parametric structural equation model with independent errors (NPSEM-IE). The assumptions made by the FFRCISTG model can be read off from the associated single-world intervention graphs
(SWIG); see richardson2013single,shpitser2022multivariate.]
represented by an ADMG $\gG$. The most widely used approach is to adjust for a set of variables $S$ that controls for confounding. Recall that $Y(x)$ denotes the potential outcome of $Y$ when $X$ is intervened on and set to level $x$.

Let $\gG$ be an ADMG over vertex set $\sV$. For distinct $X,Y \in \sV$
such that $X \notin \de(Y)$, we say a set $S \subseteq \sV \setminus \{X,Y\}$
controls for confounding between $(X,Y)$, or $X$ and $Y$ are unconfounded, if for every observed level $x$ of $X$, $Y(x)$ and $X$ are conditionally independent given $S$ under the causal model represented by $\gG$.

A set $S \subseteq \sV \setminus \{X,Y\}$ is guaranteed to control for confounding if it
satisfies the celebrated back-door criterion [Pearl, 1993] on $\gG$:

* $S$ contains no descendant of $X$, and

* there is no m-connected path from $X$ to $Y$ given $S$ with an arrowhead into $X$.

Further, <cit.> showed that this criterion is
complete in the following sense: given any set $S'
\subseteq \sV \setminus \{X,Y\}$ that controls for confounding under
the causal model represented by $\gG$, the set $S' \setminus \de(X)$
must satisfy the back-door criterion. Because set $S' \setminus \de(X)$
is no bigger than $S'$ and also controls for confounding,
it suffices to only consider those $S$ that do not contain descendants of $X$.
We will stick to this convention for the rest of this paper.

§ CONFOUNDING PATHS, ARCS AND SUFFICIENT ADJUSTMENT SETS

Despite the well-established notion of unconfoundedness or no (unmeasured)
confounding (<Ref>), it may come as a surprise that
giving a positive definition of confounding is more difficult. In
this section, we reformulate Pearl's back-door criterion symmetrically in terms of
confounding paths, which are structures in the graph that induce
confounding between the two endpoints.

Consider an ADMG $\gG$ over a vertex set $\sV$. For distinct $A,B
\in \sV$,
let $\sP_{\gG}(A \mconn B)$ denote the set of all paths from $A$ to
$B$ in $\gG$, and $\sP_{\gG}(A \rightsquigarrow B)$ denote the subset
of all directed paths. Define the set of confounding paths
from $A$ to $B$ as

\[
\sP_{\gG}(A \confpath B) := \{\pi \in \sP_{\gG}(A \mconn B):  \text{$\pi$
has two endpoint arrowheads}\}.
\]

Those confounding paths without colliders are called confounding arcs:

\[
\sP_{\gG}(A \confarc B) := \{\pi \in \mathcal{P}_{\gG}(A
\confpath B): \pi \text{ has no collider} \}.
\]

A confounding arc immediately induces non-causal
association between the endpoints when none of its non-endpoint vertices is conditioned on.
A confounding arc between $A$ and $B$ is essentially two directed paths
of the form

\[
A \leftdirpath U_1 \rightdirpath B \quad \text{or} \quad A
\leftdirpath U_1 \leftrightarrow U_2 \rightdirpath B.
\]

As our notation `$\confpath$' suggests, a
confounding path is either a confounding arc or a concatenation of
multiple confounding arcs. In the latter case, the confounding path
may induce non-causal association when all the colliders (or their descendants) are
conditioned on. To further describe paths that are m-connected given a set $C$,
we adopt the following notation.

For distinct $A,B \in \sV$ and $C \subseteq \sV \setminus \{A,B\}$, define

\begin{align*}
\sP_{\gG}(A \mconn B \mid C) &:= \{\pi \in \sP_{\gG}(A \mconn B): \pi \text{~is m-connected given $C$}\}, \\
\sP_{\gG}(A \rightsquigarrow B \mid C) &:= \{\pi \in \sP_{\gG}(A \rightsquigarrow B): \pi \text{~is m-connected given $C$}\}, \\
\sP_{\gG}(A \confpath B \mid C) &:= \{\pi \in \sP_{\gG}(A \confpath B): \pi \text{~is m-connected given $C$}\}, \\
\sP_{\gG}(A \confarc B \mid C) &:= \{\pi \in \sP_{\gG}(A \confarc B): \pi \text{~is m-connected given $C$}\}.
\end{align*}

By definition, we have

\[
\sP_{\gG}(A \confarc B \mid C) \subseteq \sP_{\gG}(A \confpath B
\mid C).
\]

Also, observe that when no variable is conditioned on, a m-connected
confounding path must be a confounding arc, i.e.
\[
\sP_{\gG}(A \confpath B \mid \emptyset) = \sP_{\gG}(A \confarc B
\mid \emptyset) = \sP_{\gG}(A \confarc B).
\]

Thus, in general, we have

\[ \sP_{\gG}(A \confpath B \mid \emptyset) \neq \sP_{\gG}(A \confpath B), \]

so `$\emptyset$' on the left hand side cannot be
omitted. Furthermore, we have

\[
\sP_{\gG}(A \confpath B) = \bigcup_{C \subseteq \sV \setminus \{A,B\}} \sP_{\gG}(A
\confpath B \mid C).
\]

Recall that in <Ref> we write

\[ A \mconn B \mid C \;\iff\; \text{$A$ and $B$ are m-connected given $C$} \;\iff\; \sP_{\gG}(A \mconn B \mid C) \neq \emptyset, \]

\[A \msep B \mid C \;\iff\; \text{$A$ and $B$ are m-separated given $C$} \;\iff\; \sP_{\gG}(A \mconn B \mid C) = \emptyset. \]

Similarly, we define the following refined relations.

Let $\gG$ be an ADMG over vertex set $\sV$. For any distinct $A,B \in
\sV$ and $C \subseteq \sV \setminus \{A,B\}$, we write

\[
A \begin{Bmatrix} \rightdirpath \\ \confarc \\
\confpath \end{Bmatrix} B \mid C \;[\gG]
\quad \iff \quad
\sP_{\gG} \left( A
\begin{Bmatrix} \rightdirpath  \\ \confarc \\
\confpath \end{Bmatrix} B \mid C \right) \neq \emptyset
\]

\[ A \begin{Bmatrix} \norightdirpath \\ \noconfarc \\
\noconfpath \end{Bmatrix} B \mid C \;[\gG] \quad \iff
\quad
\sP_{\gG} \left( A
\begin{Bmatrix} \rightdirpath  \\ \confarc \\
\confpath \end{Bmatrix} B \mid C \right) = \emptyset.
\]

Note that the relations above pertaining to `$\confarc$' and `$\confpath$' are symmetric in $A$ and $B$. The result below directly follows from definition.

For $\tilde{C} \subseteq C \subseteq \sV \setminus \{A, B\}$, we have

\[ A \rightdirpath B \mid C \implies A \rightdirpath B \mid \tilde{C}
\quad \text{and} \quad A \confarc B \mid C \implies A \confarc B
\mid \tilde{C}.\]

Next, we offer our definition of a sufficient adjustment set, which is symmetric in $X$ and $Y$, and prove its equivalence to Pearl's back-door criterion; the proof can be found
in <ref>.

Let $\gG$ be an ADMG over vertex set $\sV$. For distinct $X,Y \in
\sV$, we say $S \subseteq \sV \setminus \{X,Y\}$ is an
adjustment set if

\[S \cap (\de(X) \cup \de(Y)) = \emptyset.\]

An adjustment set $S$ is sufficient if

\[X \noconfpath Y \mid S. \]

Moreover, a sufficient adjustment set $S$ is minimal if none of its
proper subsets is also sufficient.

Let $\gG$ be an ADMG over vertex set $\sV$ and consider distinct $X,Y \in \sV$.

* If $X \notin \de(Y)$ and $S$ is a sufficient adjustment set, then $S$ controls for confounding between $(X,Y)$.

* If $X \in \an(Y)$, then $S$ is a sufficient adjustment set if and only if $S$ satisfies the back-door criterion.

In view of <Ref>, confounder selection boils down to
finding an adjustment set $S$ that blocks all the confounding paths
`$\confpath$' between $X$ and $Y$; thus $S$ necessarily blocks all
confounding arcs `$X \confarc Y$'. However, by monotonicity
(<ref>), blocking confounding arcs is considerably
easier than blocking confounding paths — expanding $S$ does
not introduce new m-connected confounding arcs but can introduce new
m-connected confounding paths due to colliders. This observation
motivates our procedure in <ref> that blocks confounding paths by blocking confounding

§ PROPERTIES OF REFINED M-CONNECTION

Our approach to confounder selection is based on iterative graph expansion, a
process that inverts a sequence of latent projections. Thus, it is important to
understand how confounding paths behave under latent projection. In
fact, similar to the ordinary m-connection/separation, their refined forms
in <ref> are also preserved by latent projection.

Let $\gG$ be an ADMG over vertex set $V$. For any  distinct $A, B \in
\sV$, $C \subseteq V \setminus \{A,B\}$, and vertex set $\tilde{V}$ such
that $V \supseteq \tilde{V} \supseteq \{A,B\} \cup C$, we have

\[
A \begin{Bmatrix} \rightdirpath \\ \confarc \\
\confpath \\ \mconn \end{Bmatrix} B \mid C \ [\gG] \quad \iff \quad
A \begin{Bmatrix} \rightdirpath \\ \confarc \\
\confpath \\ \mconn \end{Bmatrix} B \mid C \ [\gG(\tilde{V})].
\]

The last statement is the preservation of m-connection and the
preceding statements are about its refinements. <ref>
immediately implies the next result.

Let $\gG, \gG'$ be two latent projections of the same ADMG. For vertices $A,B$ and vertex set $C$ on both graphs, it holds that

\[
A \begin{Bmatrix} \rightdirpath \\ \confarc \\
\confpath \\ \mconn \end{Bmatrix} B \mid C \ [\gG] \quad \iff \quad
A \begin{Bmatrix} \rightdirpath \\ \confarc \\
\confpath \\ \mconn \end{Bmatrix} B \mid C \ [\gG'].
\]

<ref> can be further strengthened as follows:
m-connections by arcs (i.e., without colliders) are preserved by latent projection with matching
endpoint arrowheads and tails; m-connections by general paths
are also preserved by latent projection, but only endpoint arrowheads
are preserved. This means that, for example, the following implication
with only matching arrowheads is true (this can be seen from our proof
of <Ref>):

\[
A \rightsquigarrow \ast \leftrightsquigarrow B \mid C \ [\gG]
\quad \implies \quad A \halfsquigfull \ast
\leftrightsquigarrow B \mid C \ [\gG(\tilde{\sV})],
\]

but, in general,

\[
A \rightsquigarrow \ast \leftrightsquigarrow B \mid C \ [\gG]
\quad \centernot{\implies} \quad A \rightsquigarrow \ast
\leftrightsquigarrow B \mid C  \ [\gG(\tilde{\sV})].
\]

To illustrate the last point, consider
<ref>, where $\gG', \gG''$ are successive latent
projections of $\gG$ and $\gF'$ is a latent projection of $\gF$. We
have the following observations:

* The relation $A \rightsquigarrow \ast \leftsquigarrow B \mid C$ holds in $\gG$
(path $A \rightarrow E \leftrightarrow F \leftarrow B$) and $\gG'$
(path $A \rightarrow C \leftrightarrow F \leftarrow B$) but not in

* The relation $A \rightsquigarrow \ast \leftrightsquigarrow D
\mid C$ holds in $\gG$ (path $A \rightarrow E \leftrightarrow F
\leftarrow B \rightarrow D)$ and $\gG'$ (path $A \rightarrow C
\leftrightarrow F \leftarrow B \rightarrow D$), but not in
$\gG''$. Instead, $A \confpath D \mid C$ holds in $\gG''$ (path
$A \leftarrow B \rightarrow D$).

* With wildcard `+' denoting one or more colliders, the relation $A \leftrightsquigarrow + \leftrightsquigarrow B \mid C$ holds in
$\gF$ (path $A \leftarrow D \leftrightarrow E \leftrightarrow B$)
but not in $\gF'$.

rv/.style=circle,inner sep=1pt,draw,font=,
lv/.style=circle,inner sep=1pt,fill=gray!50,draw,font=,
fv/.style=rectangle,inner sep=1.5pt,fill=gray!20,draw,font=,
node distance=12mm, >=stealth
[name=A, rv]$A$;
[name=E, rv, right of=A]$E$;
[name=F, rv, right of=E]$F$;
[name=B, rv, right of=F]$B$;
[name=D, rv, right of=B]$D$;
[name=C, rv, below of=A, xshift=5mm]$C$;
[->, thick] (A) to (E);
[<->, thick] (E) to (F);
[<-, thick] (F) to (B);
[->, thick] (B) to (D);
[->, thick, bend right] (F) to (A);
[->, thick] (A) to (C);
[->, thick] (E) to (C);
[right of=C, xshift=10mm, yshift=-7mm]$\gG$;
[xshift=6cm] [name=A, rv]$A$;
[name=F, rv, right of=A]$F$;
[name=B, rv, right of=F]$B$;
[name=D, rv, right of=B]$D$;
[name=C, rv, below of=A, xshift=5mm]$C$;
[->, thick] (F) to (A);
[->, thick] (B) to (F);
[->, thick] (B) to (D);
[->, thick] (A) to (C);
[<->, thick] (F) to (C);
[right of=C, xshift=2mm, yshift=-7mm]$\gG'$;
[xshift=11cm] [name=A, rv]$A$;
[name=B, rv, right of=A]$B$;
[name=D, rv, right of=B]$D$;
[name=C, rv, below of=A, xshift=5mm]$C$;
[->, thick] (B) to (A);
[->, thick] (B) to (D);
[->, thick] (A) to (C);
[<->, thick, bend right] (A) to (C);
[right of=C, xshift=-3mm, yshift=-7mm]$\gG''$;
[yshift=-3cm] [name=A, rv]$A$;
[name=D, rv, right of=A]$D$;
[name=E, rv, right of=D]$E$;
[name=B, rv, right of=E]$B$;
[name=C, rv, below of=D]$C$;
[->, thick] (D) to (A);
[<->, thick, bend left] (D) to (E);
[->, thick] (E) to (D);
[<->, thick] (E) to (B);
[->, thick] (D) to (C);
[right of=C, xshift=-5mm, yshift=-7mm]$\gF$;
[yshift=-3cm, xshift=6cm] [name=A, rv]$A$;
[name=D, rv, right of=A]$D$;
[name=B, rv, right of=D]$B$;
[name=C, rv, below of=D]$C$;
[->, thick] (D) to (A);
[<->, thick] (D) to (B);
[->, thick] (D) to (C);
[below of=C, yshift=4mm]$\gF'$;

$\gG'$ is a latent projection of $\gG$ and $\gG''$ is a further projection of $\gG'$; $\gF'$ is a projection of $\gF$.

§.§ Proof of <Ref>

We prove <Ref> by re-characterizing (refined)
m-connection using m$^{*}$-connected simple walks, denoted as $\sW^s(\cdot)$, as a proxy to m-connected paths. In particular, the
first equivalence in <Ref> follows from
<Ref> below via the following
equivalence diagram:

$A \rightdirpath B \mid C\;[\gG]$     $\overset{\text{Def.}\ \ref{def:conf-relation}}{\iff}$
$\sP_{\gG}(A \rightdirpath B \mid C) \neq \emptyset$
$\overset{\text{Lem.}\ \ref{lem:walk-path}}{\iff}$
$\sW_{\gG}^s(A \rightdirpath B \mid C) \neq
\emptyset$

${\bigg \Updownarrow}$
Lem.                                            <ref>

$A \rightdirpath B \mid C\;[\gG(\tilde{V})]$     $\overset{\text{Def.}\ \ref{def:conf-relation}}{\iff}$
$\sP_{\gG(\tilde{V})}(A \rightdirpath B \mid C) \neq \emptyset$
$\overset{\text{Lem.}\ \ref{lem:walk-path}}{\iff}$
$\sW_{\gG(\tilde{V})}^s(A \rightdirpath B \mid C) \neq
\emptyset$.

Here, $\sW_{\gG}^s(A \rightdirpath B \mid C)$ is the collection of all
simple, m$^{*}$-connected directed walks from $A$ to $B$ given $C$;
the notions of m$^{*}$-connectedness and simple walks are introduced shortly. All other equivalences in <Ref> can be proved in exactly the same way.

Recall that a walk is a sequence of adjacent edges of any type or
orientation. Next we briefly explain why reasoning with walks instead
of paths simplifies the proof. Given a path, one may have to look beyond
the path to determine its m-connectedness.
That is, the notion of a m-connected path is relative to the graph:
the same path may be m-connected in one graph but not
m-connected in another. For example, in
<Ref>, the path $A \rightarrow D
\leftarrow B$ is m-connected given $C$ in $\gG_1$ but not m-connected
given $C$ in $\gG_2$. This issue can be avoided by defining a notion
of m-connection for walks, which we call m$^{*}$-connection, that does not involve the descendants of any collider; this notion has been used in the literature, e.g., van der Zander et al., 2019.

rv/.style=circle,inner sep=1pt,draw,font=,
lv/.style=circle,inner sep=1pt,fill=gray!50,draw,font=,
fv/.style=rectangle,inner sep=1.5pt,fill=gray!20,draw,font=,
node distance=12mm, >=stealth
[name=A, rv]$A$;
[name=D, rv, right of=A]$D$;
[name=B, rv, right of=D]$B$;
[name=C, rv, below of=D]$C$;
[->, thick] (A) to (D);
[->, thick] (B) to (D);
[->, thick] (D) to (C);

rv/.style=circle,inner sep=1pt,draw,font=,
lv/.style=circle,inner sep=1pt,fill=gray!50,draw,font=,
fv/.style=rectangle,inner sep=1.5pt,fill=gray!20,draw,font=,
node distance=12mm, >=stealth
[name=A, rv]$A$;
[name=D, rv, right of=A]$D$;
[name=B, rv, right of=D]$B$;
[name=C, rv, below of=D]$C$;
[->, thick] (A) to (D);
[->, thick] (B) to (D);

Two simple ADMGs illustrating the difference between
m-connection and m$^{*}$-connectedness.

A walk is said to be m$^{*}$-connected given a vertex set $C$ if
every non-collider on the walk is not contained by $C$ and every
collider on the walk is contained by $C$.

In <Ref>, the walk $A \rightarrow D
\leftarrow B$ is not m$^{*}$-connected given $C$ in both $\gG_1$ and
$\gG_2$. Yet, the walk $A \rightarrow D \rightarrow C \leftarrow
D \leftarrow B$ (present in $\gG_1$ but not in $\gG_2$) is always m$^{*}$-connected given $C$, irrespective of the graph where the walk resides.

Let $\sW_{\gG}(A \mconn B \mid C)$ denote all the m$^{*}$-connected walks from
$A$ to $B$ given $C$ in an ADMG $\gG$. Other notations are
introduced in a similar way. Specifically, we write

\begin{align*}
\sW_{\gG}(A \confpath B \mid C) &:= \{\pi \in \sW_{\gG}(A \mconn B
\mid C):  \text{$\pi$
has two endpoint arrowheads}\}, \\
\sW_{\gG}(A \confarc B \mid C) &:= \{\pi \in \sW_{\gG}(A
\confpath B \mid C): \pi \text{ has no collider} \}.
\end{align*}

Note that $\sP(A \confarc B \mid C) \subseteq \sW(A
\confarc B \mid C)$ is true because confounding arcs have no
colliders, but
$\sP(A \confpath B \mid C) \subseteq \sW(A \confpath B \mid C)$ is
generally not true because a m-connected path may not be
m$^{*}$-connected. Nevertheless, it is shown below that the
existence of m-connected paths, as one may
expect, is equivalent to the existence of m$^{*}$-connected walks.

Since we are interested in the preservation of endpoint arrowheads by
latent projection, we will focus on simple walks; see
<ref> below.

A walk is simple if its endpoints are visited only
once by the walk.

We add a superscript `$s$' to $\sW(\cdot)$ to indicate that only simple walks are concerned.
For example, $\sW^s_{\gG}(A \confpath B \mid C)$ denotes all the m$^{*}$-connected
confounding simple walks from $A$ to $B$ given $C$, i.e.,

\[
\sW^s_{\gG}(A \confpath B \mid C) := \left\{\pi \in \sW_{\gG}(A \confpath
B \mid C):\text{$\pi$ is simple}\right\}.
\]

It is easy to see that there exists a m$^{*}$-connected walk between
$A$ and $B$ given $C$ if and only if there exists a m$^{*}$-connected
simple walk between $A$ and $B$ given $C$, that is,

\[
\sW_{\gG}(A \mconn B \mid C) = \emptyset
\quad \iff \quad \sW_{\gG}^s(A \mconn B \mid C) = \emptyset.
\]

As mentioned earlier, <ref> is proved by applying the next two key lemmas.
<ref> shows that refined m-connection can be
re-characterized in terms of m$^{*}$-connected simple walks.
Further, <ref> shows that m$^{*}$-connected simple walks are preserved by latent projection. The proofs of these lemmas are deferred to <Ref>.

Let $\gG$ be an ADMG over vertex set $\sV$. For any distinct $A,
B \in \sV$ and $C \subseteq \sV \setminus \{A,B\}$, we have

\[
\sP_{\gG} \left( A
\begin{Bmatrix} \rightdirpath  \\ \confarc \\
\confpath \\ \mconn \end{Bmatrix} B \mid C \right) \neq \emptyset
\quad \iff \quad
\sW^s_{\gG} \left( A
\begin{Bmatrix} \rightdirpath  \\ \confarc \\
\confpath \\ \mconn \end{Bmatrix} B \mid C \right) \neq \emptyset.
\]

Let $\gG$ be an ADMG over vertex set $V$. For any  distinct $A, B \in
\sV$, $C \subseteq V \setminus \{A,B\}$ and vertex set $\tilde{V}$ such
that $V \supseteq \tilde{V} \supseteq \{A,B\} \cup C$, we have

\[
\sW_{\gG}^s \left( A \begin{Bmatrix} \rightdirpath \\ \confarc \\
\confpath \\ \mconn \end{Bmatrix} B \mid C  \right) \neq \emptyset \quad
\iff \quad
\sW_{\gG(\tilde{V})}^s \left( A \begin{Bmatrix} \rightdirpath \\ \confarc \\
\confpath \\ \mconn \end{Bmatrix} B \mid C  \right) \neq \emptyset.
\]

For an m$^{*}$-connected walk that is not simple, there may not exist a
corresponding m-connected path with matching endpoint
arrowheads. Consider the
graph $C \rightarrow A \rightarrow B$. Although the walk $A \leftarrow C
\rightarrow A \rightarrow B$ is m$^{*}$-connected from $A$ and $B$
given the empty set, there is no m-connected path from $A$ to $B$
starting with `$A \leftarrow$'.

§.§ District criterion

From <Ref>, we derive the following simple but useful
criterion for confounder selection. In below, `$A
\leftrightarrow \ast \leftrightarrow B$' denotes a path
between $A$ and $B$ consisting of bidirected edges only. If there exists
such a path that is m-connected given $C$, we write $A \leftrightarrow
\ast \leftrightarrow B \mid C$. Symbol `$A \markovblanket B$' denotes
any path between $A$ and $B$ where every non-endpoint vertex is a collider.

For an ADMG $\gG$, consider two distinct vertices $A, B$ and a vertex set $C$ such that $A, B \notin C$.
We have

\[
A \begin{Bmatrix} \rightdirpath \\ \confarc \\
\confpath \\ \mconn \end{Bmatrix} B \mid C \  [\gG] \quad \iff
\quad A \begin{Bmatrix} \rightarrow \\ \leftrightarrow \\
\samedist \\ \markovblanket \end{Bmatrix} B \ [\gG\left(\{A,B\} \cup C\right)].
\]

Apply <ref> with $\tilde{V} = \{A,B\} \cup C$.  Because $C$ contains all vertices other than $A,B$ in $\gG(\tilde{V})$, an m-connected arc must be a single directed or bidirected edge. Further, any non-endpoint vertex on any m-connected path in $\gG(\tilde{V})$ must be a collider.

We make two further remarks. First, recall that
in the literature of graphical models, a district in an
ADMG is defined as a maximal set of vertices connected by bidirected edges (see, e.g., Evans and Richardson, 2014). That
is, $A$ and $B$ are in the same district if and only if $A \samedist B$.
By the third equivalence relation in <Ref>, an
adjustment set $S$ is sufficient for $A$ and $B$ if and only if $A$
and $B$ are in different districts of $\gG(\{A,B\} \cup S)$. We call
this the district criterion for confounder selection. It
provides a simple and useful way to check whether a set of selected
confounders is indeed sufficient. Second, the last equivalence
relation in <Ref> says that $A$ and $B$ are m-connected
given $C$ if and only if $A$ and $B$ are “collider-connected” in $\gG(\{A,B\} \cup C)$,
which is related to the notion of Markov blanket for ADMGs in

§.§ Graphoid-like properties

In this subsection, we consider extending the refined m-connection/separation relations in <ref> to disjoint sets $A, B, C \subset \sV$. For example, we write

\[ A \confpath B \mid C \;[\gG] \quad \iff \quad a \confpath b \mid C \text{ for some $a \in A$, $b \in B$} \]

\[ A \noconfpath B \mid C \;[\gG] \quad \iff \quad a \noconfpath b \mid C \text{ for every $a \in A$, $b \in B$}. \]

In addition, following the convention in the literature, we assume $A
\noconfpath \emptyset \mid C$ holds for every disjoint $A$ and
$C$. Extension for `$\confarc$' is made
similarly. To avoid clutter, we use comma in place of `$\cup$' in
these relations, e.g., $A \confpath B,C \mid D$ stands for $A
\confpath B \cup C \mid D$.

Let $\mathcal{J}$ be a collection of tuples $\langle A, B \mid C \rangle$ for $A,B,C$ that are disjoint subsets of a ground set $\sV$. For disjoint $A,B,C,D \subset \sV$, consider the following properties:

* triviality: $\langle A, \emptyset \mid C \rangle$ for every disjoint $A,C \subset \sV$;

* symmetry: $\langle A, B \mid C \rangle \implies \langle B, A \mid C \rangle$;

* decomposition: $\langle A, B \cup C \mid D \rangle \implies \langle A, B \mid D \rangle \text{ and } \langle A, C \mid D \rangle$;

* weak union: $\langle A, B \cup C \mid D \rangle \implies \langle A, B \mid C \cup D \rangle$;

* contraction: $\langle A, C \mid D \rangle \text{ and } \langle A, B \mid C \cup D\rangle \implies \langle A, B \cup C \mid D \rangle$;

* intersection: $\langle A, B \mid C \cup D \rangle \text{ and } \langle A, C \mid B \cup D \rangle \implies \langle A, B \cup C \mid D \rangle$;

* composition: $\langle A, B \mid D \rangle \text{ and } \langle A, C \mid D \rangle \implies \langle A, B \cup C \mid D \rangle$.

We say $\mathcal{J}$ is a semi-graphoid over $\sV$, if it
satisfies (i)–(v); further, we say $\mathcal{J}$ is a graphoid
over $\sV$, if it satisfies (i)–(vi), and finally, a
compositional graphoid over $\sV$, if it satisfies (i)–(vii).

For any ADMG, it is known that m-separation `$\msep$' is a compositional graphoid [Sadeghi and Lauritzen, 2014]. However, relations induced by `$\noconfarc$' and `$\noconfpath$' are weaker than semi-graphoids; see <ref> for the proof of the next result.

Relations $\mathcal{J}_{\noconfarc}:=\{\langle A, B \mid C\rangle: A
\noconfarc B \mid C \;[\gG] \}$ and $\mathcal{J}_{\noconfpath}:=\{
\langle A, B \mid C \rangle: A \noconfpath B \mid C \;[\gG] \}$
satisfy properties (i)–(iv) and (vii) in <Ref> for any
ADMG $\gG$. Moreover, there exist ADMGs in which (v) and (vi) fail for
both relations.

§ ITERATIVE GRAPH EXPANSION

§.§ Primary adjustment set

A primary adjustment set is any adjustment set that blocks all the
confounding arcs `$\confarc$', i.e., confounding paths with no
colliders, between two vertices.
They are the building blocks when we try to find sufficient adjustment sets
by iteratively expanding the graph, a procedure that is introduced in the
next subsection.

Given two distinct vertices $A,B$ and a set $S$ such that $A,B \notin S$,
an adjustment set $C$ for $A,B$ is called primary relative to $S$ if
$A \noconfarc B \mid S \cup C$. When $S = \emptyset$, we simply say
that $C$ is a primary adjustment set for $A$ and $B$. Further, $C$ is called
minimal primary (relative to $S$) if none of its proper subsets is
primary (relative to $S$).

By definition, if $C$ is a (minimal) primary adjustment set for $A$
and $B$, it is also a (minimal) primary adjustment set for $B$ and
$A$. Further, because the relation $\noconfpath$ implies the relation
$\noconfarc$, any sufficient adjustment set must be primary, but a
primary adjustment set need not to be sufficient. For example, in the
graph $A \leftrightarrow D \leftrightarrow B$, the adjustment set
$\{D\}$ for $(A,B)$ is primary but not sufficient.

If $C$ is a minimal primary adjustment set for $A$ and $B$ relative to $S$,
then $C \cap S = \emptyset$ and $C
\subseteq \an(A) \cup \an(B)$.

Suppose $A \noconfarc B \mid S \cup \tilde{C}$ for some
$\tilde{C}$. Let $C = \tilde{C} \cap (\an(A) \cup \an(B)) \setminus
S$. It is easy to show that any confounding arc $A \confarc B$ that is not m-connected given $S \cup \tilde{C}$
remains not m-connected given $S \cup C$. Thus, $A \noconfarc B
\mid S \cup C$. The result then follows from the definition of minimal
primary adjustment set.

Let $\gG$ be an ADMG over vertex set $V$. Suppose $S \subset V$ is a
minimal sufficient adjustment set for distinct $X, Y \in V$. Then, for any
$\tilde{S} \subset S$, there exists distinct $Z_1,Z_2 \in \tilde{S} \cup
\{X,Y\}$ such that

\begin{equation} \label{eqs:completeness}
Z_1 \leftrightarrow Z_2 \;[\gG(\tilde{S} \cup \{X,Y\})] \quad
\text{and} \quad Z_1 \centernot{\leftrightarrow} Z_2 \;[\gG(S \cup
\{X,Y\})].
\end{equation}

Moreover, there exists a non-empty minimal primary
adjustment set $C \subseteq S \setminus \tilde{S}$ for $(Z_1, Z_2)$
relative to $\tilde{S} \setminus \{Z_1, Z_2\}$.

Before we prove <Ref>, note that by
<Ref>, equation (<ref>) is equivalent

\[
Z_1 \confarc Z_2 \mid \tilde{S} \cup \{X,Y\} \setminus \{Z_1,Z_2\}
\;[\gG] \quad \text{and} \quad Z_1 \noconfarc Z_2 \mid S \cup \{X,Y\} \setminus
\{Z_1,Z_2\} \;[\gG].
\]

Because $Z_1, Z_2 \in \tilde{S} \cup \{X,Y\}$ and $\tilde{S}$ is an
adjustment set, we know $Z_1$ and $Z_2$ are not descendants of $X$ or
$Y$. Therefore, we can safely remove $\{X,Y\}$ from the conditioning
sets and (<ref>) is also equivalent to

\begin{equation} \label{eqs:completeness-2}
Z_1 \confarc Z_2 \mid \tilde{S} \setminus \{Z_1,Z_2\}
\;[\gG] \quad \text{and} \quad Z_1 \noconfarc Z_2 \mid S \setminus
\{Z_1,Z_2\} \;[\gG].
\end{equation}

To interpret the conclusions of this theorem, imagine trying to find a
minimal sufficient
adjustment set $S$ by iteratively adding vertices. Suppose $\tilde{S}
\subseteq S$ is our current estimate. As long as $\tilde{S}$ is not
yet sufficient, we can find $Z_1, Z_2 \in \tilde{S} \cup \{X,Y\}$ such
that there is a confounding arc between them that is not blocked by
$\tilde{S}$. To block it, we can try to find a primary adjustment set
$C$ for $Z_1, Z_2$ relative to $\tilde{S}$ and add $C$ to $\tilde{S}$ and
make $\tilde{S} \cup C$ our next estimate. This theorem states that
for at least one choice of $C$, the new estimate $\tilde{S} \cup C$
will remain a subset of (and possibly the same as) $S$. If
$\tilde{S} \cup C$ is still not sufficient, we may iterate the process
until we eventually obtain the set $S$. In other words, <Ref>
essentially shows that all minimal sufficient adjustment
sets for $(X,Y)$ can be found by recursively expanding a bidirected
edge with its minimal primary adjustment sets; this is the basis of
<Ref> below.

Because $\tilde{S}$ is a proper subset of
a minimal sufficient adjustment set $S$, $\tilde{S}$ is still an
adjustment set but is not sufficient. By <ref>, we have

\[ X \confpath Y \mid \tilde{S} \;[\gG] \quad \implies \quad X \samedist Y \;[\gG(\tilde{S} \cup \{X,Y\})]. \]

Therefore, there exists a bidirected path

\[ X=D_0 \leftrightarrow \dots \leftrightarrow D_{k} = Y, \quad k \geq 1 \quad  \text{in } \gG(\tilde{S} \cup \{X,Y\}). \]

We claim that there exists $j \in \{0,\dots,k-1\}$ such that $D_j
\centernot{\leftrightarrow} D_{j+1}$ in $\gG(S \cup
\{X,Y\})$. Otherwise, the same bidirected path also appears in
$\gG(S \cup \{X,Y\})$ (because $\tilde{S} \subset S$), so by <ref>,

\[ X \samedist Y \;[\gG(S \cup \{X,Y\})] \quad \implies \quad X \confpath Y \mid S, \]

contradicting the assumption that $S$ is sufficient. By our choice, we have
$D_j, D_{j+1} \in \tilde{S} \cup \{X,Y\}$ and $D_j \leftrightarrow
D_{j+1}$ in $\gG(\tilde{S} \cup \{X,Y\})$. Hence, we have shown the
existence of $(D_j, D_{j+1})$, rewritten as $(Z_1, Z_2)$, as desired.

For the second conclusion, observe that <ref> holds,
that is, $S \setminus \{Z_1,Z_2\}$ is primary for $(Z_1, Z_2)$ but
$\tilde{S} \setminus \{Z_1,Z_2\}$ is not. The existence of such
a minimal primary adjustment set $C$ then follows from the definition.

§.§ Iterative graph expansion algorithm

We now introduce our procedure ConfounderSelect that
is based on two sub-routines: SelectEdge and FindPrimary. See
<Ref> for the pseudo-code of an implementation
using a priority queue $\mathcal{Q}$ that admits a Pop and a Push
operation; see also <ref> for a recursive
version of the algorithm that is shorter but less flexible. We leave
the choices of the priority index and of the SelectEdge
subroutine to the next subsection, as they do not affect the validity of
the algorithm. In practice, it is through the FindPrimary
subroutine that the information about the underlying graph is elicited
from the user; we discuss its implementation in <ref>.

In this algorithm, all possible bidirected edges in the
current graph
$\gG(\bar{S})$, where $\bar{S}:=S \cup \{X,Y\}$ and $S$ is our working
adjustment set, are classified into three kinds:

* the set $\mathcal{B}_n$ that contains all the bidirected edges that are absent or already blocked,

* the set $\mathcal{B}_y$ that contains all the bidirected edges that
exist or assumed to exist, which the algorithm will not attempt to block, and

* the set $\mathcal{B}_u := (\bar{S} \times \bar{S}) \setminus
(\mathcal{B}_n \cup \mathcal{B}_y)$ that contains all the uncertain
bidirected edges that the algorithm will attempt to block.

In other words, the algorithm maintains $\mathcal{B}_u \cup
\mathcal{B}_y$ as a superset of the bidirected edges in
$\gG(\bar{S})$. In each iteration, the subroutine $\Call{SelectEdge}{X,Y,S,\mathcal{B}_y,\mathcal{B}_n}$ selects an
uncertain bidirected edge $\pi$ from $\mathcal{B}_u$.
The subroutine $\textsc{FindPrimary}$ is then called to find the
primary adjustment sets for the two end points of $\pi$ relative to the current
adjustment set.
If $\pi$ is already blocked by the current adjustment set (i.e., the empty set
is returned as a primary adjustment set), then $\pi$ is moved to $\mathcal{B}_n$.
Otherwise, the algorithm
then attempts to move $\pi$ to $\mathcal{B}_n$ by expanding $\pi$ with
every primary adjustment set that is returned by the subroutine
$\textsc{FindPrimary}$. Finally, it attempts to make no expansion by moving
$\pi$ to $\mathcal{B}_y$. Because the vertex set $\sV$ is assumed
to be finite, this algorithm will eventually terminate.

Let $\gG$ be an ADMG over vertex set $\sV$. The following two statements hold
for any distinct $X,Y \in \sV$ such that $X \notin \de(Y)$.

* Suppose for any $A,B \in \sV$ and $S' \subseteq \sV \setminus \{A,B\}$,
when $\Call{FindPrimary}{A,B; S'} \neq \emptyset$,
every $C \in \Call{FindPrimary}{A,B; S'}$ is
a primary adjustment set for $A,B$ relative to $S'$ in $\gG$. Then
every element in the output of $\Call{ConfounderSelect}{X,Y}$ is a
sufficient adjustment set for $X,Y$.

* Suppose further that $\Call{FindPrimary}{A,B; S'}$ contains every minimal primary adjustment set for $A,B$ relative to $S'$ in $\gG$. Then the output of $\Call{ConfounderSelect}{X,Y}$ contains all minimal sufficient adjustment sets for $X,Y$.

Statement 1 says that the graph expansion algorithm is sound. It follows
from the district criterion (<Ref>), as an adjustment
set $S$ is only added to the output $\mathcal{R}$ in lines 8-11 of
<Ref> when $X$ and $Y$ are not connected by
bidirected edges in $\mathcal{B}_y \cup \mathcal{B}_u$ (and hence in
$\gG(\bar{S})$). Statement 2
says that the graph expansion algorithm is complete for identifying
minimal sufficient adjustment sets. It directly follows from

Confounder selection via iterative graph expansion

[1] ConfounderSelect$X$, $Y$
$\mathcal{R} = \{ \}$ Set of sufficient
adjustment sets
$\mathcal{Q} = \Call{PriorityQueue}{(\emptyset, \emptyset,\emptyset)}$
Initial graph has a possible edge $X \dbarrow Y$
$\mathcal{Q} \neq \emptyset$
$(S,\mathcal{B}_y,\mathcal{B}_n) = $
Pop$\mathcal{Q}$  [t].34$S$: current adjustment set
$\mathcal{B}_y$: edges not to be expanded
$\mathcal{B}_n$: absent or blocked edges
$\bar{S} = S \cup \{X,Y\}$
$X \samedist Y$ by edges in $\mathcal{B}_y$ Fails the district criterion
$X \diffdist Y$ by edges in $(\bar{S}
\times \bar{S}) \setminus \mathcal{B}_n$ Satisfies the district criterion
$\mathcal{R} = \mathcal{R} \cup \{S\}$
$(A,B) = \pi = $ SelectEdge$X$, $Y$, $S$, $\mathcal{B}_y$, $\mathcal{B}_n$ $\pi$ is selected from $(\bar{S} \times \bar{S}) \setminus (\mathcal{B}_y \cup \mathcal{B}_n)$
$\mathcal{L} = $ FindPrimary$(A,B); S \setminus
\{A,B\}$
$\emptyset \in \mathcal{L}$
Push$\mathcal{Q}$, ($S$, $\mathcal{B}_y$,
$\mathcal{B}_{n} \cup \{\pi\}$) $\pi$ need not be expanded
$C \in \mathcal{L}$
Push$\mathcal{Q}$, ($S \cup C$, $\mathcal{B}_y$,
$\mathcal{B}_{n} \cup \{\pi\}$) Expand $\pi$ by each primary adjustment set
Push$\mathcal{Q}$, ($S$, $\mathcal{B}_y \cup \{\pi\}$,
$\mathcal{B}_{n}$) Not to expand $\pi$

§.§ Practical considerations

<Ref> provides a sound and complete template
for confounder selection, which relies on subroutines FindPrimary, SelectEdge
and a priority index specified for the queue $\mathcal{Q}$.
In practice, instead of finding all the
(minimal) sufficient adjustment sets, often the goal is to find one such
set quickly, i.e., with only a few attempts of graph expansion.
This goal can be facilitated by choosing SelectEdge and the
priority index properly, as discussed below. We leave the
implementation of FindPrimary to the next subsection.

To find a (minimal) sufficient adjustment set quickly, we recommend the following min-cut strategy. Suppose the priority queue $\mathcal{Q}$ is implemented such that (1) Pop($\mathcal{Q}$) returns an element with the lowest index, and (2) in case of a tie, returns the element that is last pushed to $\mathcal{Q}$. We choose the priority index to be

\[\text{min-cut}(S,\mathcal{B}_y,\mathcal{B}_n) := \text{minimal number of edges removed from $(\bar{S} \times \bar{S}) \setminus (\mathcal{B}_y \cup \mathcal{B}_n)$ to disconnect $X$ and $Y$}.\]

In case of $X \samedist Y$ by edges in $\mathcal{B}_y$, let $
\text{min-cut}(S,\mathcal{B}_y,\mathcal{B}_n) := \infty$. Because
$\text{min-cut}=0$ whenever the district criterion is satisfied (line
9, <ref>), this choice prioritizes those
candidates needing the fewest number of expansions. Accordingly, we
recommend a subroutine SelectEdge($X$, $Y$, $S$, $\mathcal{B}_y$,
$\mathcal{B}_n$) that returns an edge that lies on the min-cut, with
ties broken in a way that best suits the problem. This strategy is
adopted by the examples in <Ref> and <Ref>,
where the min-cut of the popped graph is marked in red.

§.§ Finding primary adjustment sets

Finding primary adjustment sets for $A$ and $B$ relative to $S$

[1] FindPrimary$A$, $B$; $S$,
$\mathcal{L} = \{\}$ Set of primary adjustment sets relative to $S$
$\mathcal{T} = \Call{PriorityQueue}{S}$
Initialize with the current adjustment set
$\mathcal{T} \neq \emptyset$
$T = \Call{Pop}{\mathcal{T}}$
$C = \Call{CommonCause}{A,B; T}$ Find
a common cause that is not blocked by $T$
$C ~\text{is}~ \textsc{null}$ $T$ is primary
$L = T \setminus S$
Remove redundant vertices
$Z \in L$
S \cup L \setminus \{Z\}}$ is null
$L = L \setminus \{Z\}$
$\mathcal{L} = \mathcal{L} \cup \{L\}$
$\Call{Push}{\mathcal{T}, T \cup \{C\}}$
Add the common cause to $T$
$M_i \in \Call{FindMediator}{A,B;C,S}$
$\Call{Push}{\mathcal{T}, T \cup
Add mediators to $T$

Given two vertices $A,B$ and a set $S$ such that $A,B
\notin S$, recall that an adjustment set $S'$ for $A,B$ is primary relative to $S$
if $A \noconfarc B \mid S \cup S'$. Suppose $\bar{\gG}$ is the underlying causal
DAG over vertex set $\bar{\sV}$. By <ref>, $A \noconfarc B \mid S \cup S'$
holds if and only if the set of common causes of $A$ and $B$ not blocked by $S \cup S'$ is empty, that is

\[ \mathcal{C}(A,B; S \cup S')  := \{C \in \bar{\sV}: C \rightdirpath A \mid S, S' \text{ and } C \rightdirpath B \mid S, S' \text{ in $\bar{\gG}$} \} = \emptyset.\]

Consider <ref> for an iterative procedure that identifies
primary adjustment sets. It uses three subroutines: CommonCause,
FindMediator, and IsObserved.
If $\mathcal{C}(A,B;S) \neq \emptyset$, the subroutine
$\Call{CommonCause}{A,B; S}$ returns a vertex from
$\mathcal{C}(A,B;S)$, i.e., a common cause of $A$ and $B$ whose causal
paths to $A$ and $B$ are not blocked by $S$; otherwise,
$\Call{CommonCause}{A,B; S}$ returns null.
For $C \in \mathcal{C}(A,B;S)$, the subroutine
$\Call{FindMediator}{A,B;C,S}$ then returns a collection of
observed adjustment sets $\{M_i \subseteq \sV \}$ of $A,B$ such
\[C \not \rightsquigarrow A \mid S, M_i\quad \text{or} \quad C
\not \rightsquigarrow B \mid S, M_i \quad \text{in $\bar{\gG}$}.\]

These subroutines can be formulated in terms of questions in plain language, which we discuss in <ref>.

The procedure FindPrimary calls CommonCause
iteratively in a similar way that ConfounderSelect calls
FindPrimary. If CommonCause is null, then the
current adjustment set is primary and one can further trim this set to
obtain a minimal primary adjustment set when the option
is set to  (see line 9-17 in
<Ref>). Otherwise, we need to
block the confounding arc $A
\leftsquigarrow C \rightsquigarrow B$ by adding
either $C$ or mediators on the $C \rightsquigarrow A$ or $C
\rightsquigarrow B$ paths (obtained by FindPrimary) to
$S$, if these variables can be observed.
When implementing this algorithm, it may be desirable to use a
priority queue to store candidate sets to prioritize smaller
adjustment sets.

§ EXAMPLE

rv/.style=circle,inner sep=1pt,draw,font=,
lv/.style=circle,inner sep=1pt,fill=gray!50,draw,font=,
fv/.style=rectangle,inner sep=1.5pt,fill=gray!20,draw,font=,
node distance=12mm, >=stealth
[rv] (X) $X$;
[right of=X] (l0) ;
[rv, right of=l0] (I) $I$;
[right of=I] (l1) ;
[rv, right of=l1] (Y) $Y$;
[rv, above of=X, yshift=5mm] (T) $T$;
[rv, above of=I] (C) $C$;
[rv, above of=l0] (P) $P$;
[rv, above of=l1] (N) $N$;
[rv, above of=P] (G) $G$;
[rv, above of=G] (O) $O$;
[rv, above of=C, yshift=5mm] (F) $F$;
[rv, above of=N, yshift=12mm] (E) $E$;
[rv, above of=Y] (W) $W$;
[rv, above of=W] (D) $D$;
[->, thick] (X) – (I);
[->, thick] (I) – (Y);
[->, thick] (T) – (X);
[->, thick] (T) – (P);
[->, thick] (C) – (P);
[->, thick] (C) – (I);
[->, thick] (N) – (I);
[->, thick] (N) – (Y);
[->, thick] (O) – (T);
[->, thick] (O) – (F);
[->, thick] (E) – (F);
[->, thick] (E) – (D);
[->, thick] (E) – (N);
[->, thick] (D) – (W);
[->, thick] (D) – (N);
[->, thick] (W) – (Y);
[->, thick] (F) – (N);
[->, thick] (F) – (G);
[->, thick] (G) – (X);

A DAG model in Shrier and Platt, 2008.

We use the DAG in <Ref> taken from
Shrier and Platt, 2008 to illustrate the iterative graph expansion
algorithm. In this example, the treatment $X$ is the warming up prior to
exercise and the outcome $Y$ is injury, and this DAG was used by
Shrier and Platt, 2008 to select confounders using the back-door
criterion. In <ref>, we provide another example that involves unobserved variables.

When applying the graph expansion procedure, each iteration is indexed
by a tuple $(S,
\mathcal{B}_y, \mathcal{B}_n)$ associated with a graph that consists
of bidirected edges on vertices $\bar{S} = S \cup \{X,Y\}$. In below, we use
$\color{blue} \barrow$ to indicate bidirected edges in $\mathcal{B}_y$
that are not to be expanded, and $\dbarrow$ to indicate bidirected
edges in $(\bar{S} \times \bar{S}) \setminus (\mathcal{B}_y \cup
\mathcal{B}_n)$ that can be further expanded. In addition, we
highlight the edge $\pi$ chosen by SelectEdge with
$\color{red} \dbarrow$ and indicate the
graph popped from the queue with a box. The superscript of each box
indicates the min-cut of the popped graph and in each iteration a graph with the smallest min-cut is popped from the queue; see
<Ref>. For this example, we assume
the subroutine FindPrimary returns all minimal primary
adjustment sets (i.e., option ), so by <ref> the procedure is guaranteed to find all the
minimal sufficient adjustment sets.

* We start with

\[  \mathcal{Q} = \biggl[\; \boxed{\begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\draw[<->, dashed, thick, color=red] (X) -- (Y);
\end{tikzpicture}}^{\,\color{red} 1} \; \biggr], \quad \mathcal{R}=\{\}. \]

* We have

\[ \textsc{FindPrimary}(X,Y; \emptyset, \texttt{True}) = \left\{\{F\}, \{T,G\}, \{N,G\}, \{O,G\}, \{N,D\}, \{N,W\}, \{N,E\} \right\} \]

\begin{multline*}
\mathcal{Q} = \biggl[\; \boxed{\begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, above of=X, yshift=-0.6cm, xshift=0.8cm] (F) {$F$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\draw[<->,dashed, thick, color=red] (F) -- (X);
\draw[<->,dashed, thick] (F) -- (Y);
\end{scope} \end{tikzpicture}}^{\,\color{red} 1} \quad \begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (T) {$T$};
\node[rv, above of=Y, yshift=-0.3cm] (G) {$G$};
\draw[<->, dashed, thick] (T) -- (X);
\draw[<->, dashed, thick] (T) -- (Y);
\draw[<->, dashed, thick] (G) -- (X);
\draw[<->, dashed, thick] (G) -- (Y);
\draw[<->, dashed, thick] (T) -- (G);
\end{scope} \begin{scope}[xshift=3cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (N) {$N$};
\node[rv, above of=Y, yshift=-0.3cm] (G) {$G$};
\draw[<->, dashed, thick] (N) -- (X);
\draw[<->, dashed, thick] (N) -- (Y);
\draw[<->, dashed, thick] (G) -- (X);
\draw[<->, dashed, thick] (G) -- (Y);
\draw[<->, dashed, thick] (N) -- (G);
\end{scope} \begin{scope}[xshift=6cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (O) {$O$};
\node[rv, above of=Y, yshift=-0.3cm] (G) {$G$};
\draw[<->, dashed, thick] (O) -- (X);
\draw[<->, dashed, thick] (O) -- (Y);
\draw[<->, dashed, thick] (G) -- (X);
\draw[<->, dashed, thick] (G) -- (Y);
\draw[<->, dashed, thick] (O) -- (G);
\end{scope} \begin{scope}[xshift=9cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (N) {$N$};
\node[rv, above of=Y, yshift=-0.3cm] (D) {$D$};
\draw[<->, dashed, thick] (N) -- (X);
\draw[<->, dashed, thick] (N) -- (Y);
\draw[<->, dashed, thick] (D) -- (X);
\draw[<->, dashed, thick] (D) -- (Y);
\draw[<->, dashed, thick] (N) -- (D);
\end{scope} \end{tikzpicture} \\
\begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (N) {$N$};
\node[rv, above of=Y, yshift=-0.3cm] (W) {$W$};
\draw[<->, dashed, thick] (N) -- (X);
\draw[<->, dashed, thick] (N) -- (Y);
\draw[<->, dashed, thick] (W) -- (X);
\draw[<->, dashed, thick] (W) -- (Y);
\draw[<->, dashed, thick] (N) -- (W);
\end{scope} \begin{scope}[xshift=3cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (N) {$N$};
\node[rv, above of=Y, yshift=-0.3cm] (E) {$E$};
\draw[<->, dashed, thick] (N) -- (X);
\draw[<->, dashed, thick] (N) -- (Y);
\draw[<->, dashed, thick] (E) -- (X);
\draw[<->, dashed, thick] (E) -- (Y);
\draw[<->, dashed, thick] (N) -- (E);
\end{scope} \begin{scope}[xshift=6cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\draw[<->, thick, color=blue] (X) -- (Y);
\end{scope} \end{tikzpicture}
\;\biggr], \quad \mathcal{R}=\{\}.
\end{multline*}

* We have $\textsc{FindPrimary}((X,F); \emptyset, \texttt{True}) = \{ \{O\}, \{T\} \}$ and

\begin{multline*}
\mathcal{Q} = \biggl[\; \boxed{\begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (O) {$O$};
\node[rv, above of=Y, yshift=-0.3cm] (F) {$F$};
\draw[<->, dashed, thick, color=red] (O) -- (X);
\draw[<->, dashed, thick] (O) -- (Y);
\draw[<->, dashed, thick] (O) -- (F);
\draw[<->, dashed, thick] (F) -- (Y);
\end{scope} \end{tikzpicture}}^{\,\color{red} 1} \quad \begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (T) {$T$};
\node[rv, above of=Y, yshift=-0.3cm] (F) {$F$};
\draw[<->, dashed, thick] (T) -- (X);
\draw[<->, dashed, thick] (T) -- (Y);
\draw[<->, dashed, thick] (T) -- (F);
\draw[<->, dashed, thick] (F) -- (Y);
\end{scope} \begin{scope}[xshift=3cm]
\node[rv] (X) {$X$};
\node[rv, above of=X, yshift=-0.6cm, xshift=0.8cm] (F) {$F$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\draw[<->, thick, color=blue] (F) -- (X);
\draw[<->,dashed, thick] (F) -- (Y);
\end{scope} \begin{scope}[xshift=6cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (T) {$T$};
\node[rv, above of=Y, yshift=-0.3cm] (G) {$G$};
\draw[<->, dashed, thick] (T) -- (X);
\draw[<->, dashed, thick] (T) -- (Y);
\draw[<->, dashed, thick] (G) -- (X);
\draw[<->, dashed, thick] (G) -- (Y);
\draw[<->, dashed, thick] (T) -- (G);
\end{scope} \begin{scope}[xshift=9cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (N) {$N$};
\node[rv, above of=Y, yshift=-0.3cm] (G) {$G$};
\draw[<->, dashed, thick] (N) -- (X);
\draw[<->, dashed, thick] (N) -- (Y);
\draw[<->, dashed, thick] (G) -- (X);
\draw[<->, dashed, thick] (G) -- (Y);
\draw[<->, dashed, thick] (N) -- (G);
\end{scope} \end{tikzpicture} \\
\begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (O) {$O$};
\node[rv, above of=Y, yshift=-0.3cm] (G) {$G$};
\draw[<->, dashed, thick] (O) -- (X);
\draw[<->, dashed, thick] (O) -- (Y);
\draw[<->, dashed, thick] (G) -- (X);
\draw[<->, dashed, thick] (G) -- (Y);
\draw[<->, dashed, thick] (O) -- (G);
\end{scope} \begin{scope}[xshift=3cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (N) {$N$};
\node[rv, above of=Y, yshift=-0.3cm] (D) {$D$};
\draw[<->, dashed, thick] (N) -- (X);
\draw[<->, dashed, thick] (N) -- (Y);
\draw[<->, dashed, thick] (D) -- (X);
\draw[<->, dashed, thick] (D) -- (Y);
\draw[<->, dashed, thick] (N) -- (D);
\end{scope} \begin{scope}[xshift=6cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (N) {$N$};
\node[rv, above of=Y, yshift=-0.3cm] (W) {$W$};
\draw[<->, dashed, thick] (N) -- (X);
\draw[<->, dashed, thick] (N) -- (Y);
\draw[<->, dashed, thick] (W) -- (X);
\draw[<->, dashed, thick] (W) -- (Y);
\draw[<->, dashed, thick] (N) -- (W);
\end{scope} \begin{scope}[xshift=9cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (N) {$N$};
\node[rv, above of=Y, yshift=-0.3cm] (E) {$E$};
\draw[<->, dashed, thick] (N) -- (X);
\draw[<->, dashed, thick] (N) -- (Y);
\draw[<->, dashed, thick] (E) -- (X);
\draw[<->, dashed, thick] (E) -- (Y);
\draw[<->, dashed, thick] (N) -- (E);
\end{scope} \begin{scope}[xshift=12cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\draw[<->, thick, color=blue] (X) -- (Y);
\end{scope} \end{tikzpicture}
\;\biggr], \quad \mathcal{R}=\{\}.
\end{multline*}

* Note that $O \noconfpath X \mid F$ and hence $\emptyset \in \textsc{FindPrimary}((O,X); \{F\}, \texttt{True})$. We get

\begin{multline*}
\mathcal{Q} = \biggl[\; \boxed{\begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (O) {$O$};
\node[rv, above of=Y, yshift=-0.3cm] (F) {$F$};
\draw[<->, dashed, thick] (O) -- (Y);
\draw[<->, dashed, thick] (O) -- (F);
\draw[<->, dashed, thick] (F) -- (Y);
\end{scope} \end{tikzpicture}}^{\,\color{red} 0} \quad \begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (T) {$T$};
\node[rv, above of=Y, yshift=-0.3cm] (F) {$F$};
\draw[<->, dashed, thick] (T) -- (X);
\draw[<->, dashed, thick] (T) -- (Y);
\draw[<->, dashed, thick] (T) -- (F);
\draw[<->, dashed, thick] (F) -- (Y);
\end{scope} \begin{scope}[xshift=3cm]
\node[rv] (X) {$X$};
\node[rv, above of=X, yshift=-0.6cm, xshift=0.8cm] (F) {$F$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\draw[<->, thick, color=blue] (F) -- (X);
\draw[<->,dashed, thick] (F) -- (Y);
\end{scope} \begin{scope}[xshift=6cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (T) {$T$};
\node[rv, above of=Y, yshift=-0.3cm] (G) {$G$};
\draw[<->, dashed, thick] (T) -- (X);
\draw[<->, dashed, thick] (T) -- (Y);
\draw[<->, dashed, thick] (G) -- (X);
\draw[<->, dashed, thick] (G) -- (Y);
\draw[<->, dashed, thick] (T) -- (G);
\end{scope} \begin{scope}[xshift=9cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (N) {$N$};
\node[rv, above of=Y, yshift=-0.3cm] (G) {$G$};
\draw[<->, dashed, thick] (N) -- (X);
\draw[<->, dashed, thick] (N) -- (Y);
\draw[<->, dashed, thick] (G) -- (X);
\draw[<->, dashed, thick] (G) -- (Y);
\draw[<->, dashed, thick] (N) -- (G);
\end{scope} \end{tikzpicture} \\
\begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (O) {$O$};
\node[rv, above of=Y, yshift=-0.3cm] (G) {$G$};
\draw[<->, dashed, thick] (O) -- (X);
\draw[<->, dashed, thick] (O) -- (Y);
\draw[<->, dashed, thick] (G) -- (X);
\draw[<->, dashed, thick] (G) -- (Y);
\draw[<->, dashed, thick] (O) -- (G);
\end{scope} \begin{scope}[xshift=3cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (N) {$N$};
\node[rv, above of=Y, yshift=-0.3cm] (D) {$D$};
\draw[<->, dashed, thick] (N) -- (X);
\draw[<->, dashed, thick] (N) -- (Y);
\draw[<->, dashed, thick] (D) -- (X);
\draw[<->, dashed, thick] (D) -- (Y);
\draw[<->, dashed, thick] (N) -- (D);
\end{scope} \begin{scope}[xshift=6cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (N) {$N$};
\node[rv, above of=Y, yshift=-0.3cm] (W) {$W$};
\draw[<->, dashed, thick] (N) -- (X);
\draw[<->, dashed, thick] (N) -- (Y);
\draw[<->, dashed, thick] (W) -- (X);
\draw[<->, dashed, thick] (W) -- (Y);
\draw[<->, dashed, thick] (N) -- (W);
\end{scope} \begin{scope}[xshift=9cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (N) {$N$};
\node[rv, above of=Y, yshift=-0.3cm] (E) {$E$};
\draw[<->, dashed, thick] (N) -- (X);
\draw[<->, dashed, thick] (N) -- (Y);
\draw[<->, dashed, thick] (E) -- (X);
\draw[<->, dashed, thick] (E) -- (Y);
\draw[<->, dashed, thick] (N) -- (E);
\end{scope} \begin{scope}[xshift=12cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\draw[<->, thick, color=blue] (X) -- (Y);
\end{scope} \end{tikzpicture}
\;\biggr], \quad \mathcal{R}=\{\}.
\end{multline*}

* Because $X \diffdist Y$ in the boxed graph, a sufficient
adjustment set $\{O,F\}$ is identified. The algorithm proceeds with

\begin{multline*}
\mathcal{Q} = \biggl[\; \boxed{\begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (T) {$T$};
\node[rv, above of=Y, yshift=-0.3cm] (F) {$F$};
\draw[<->, dashed, thick, color=red] (T) -- (X);
\draw[<->, dashed, thick] (T) -- (Y);
\draw[<->, dashed, thick] (T) -- (F);
\draw[<->, dashed, thick] (F) -- (Y);
\end{scope} \end{tikzpicture}}^{\,\color{red} 1} \quad \begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, above of=X, yshift=-0.6cm, xshift=0.8cm] (F) {$F$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\draw[<->, thick, color=blue] (F) -- (X);
\draw[<->,dashed, thick] (F) -- (Y);
\end{scope}
\begin{scope}[xshift=3cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (T) {$T$};
\node[rv, above of=Y, yshift=-0.3cm] (G) {$G$};
\draw[<->, dashed, thick] (T) -- (X);
\draw[<->, dashed, thick] (T) -- (Y);
\draw[<->, dashed, thick] (G) -- (X);
\draw[<->, dashed, thick] (G) -- (Y);
\draw[<->, dashed, thick] (T) -- (G);
\end{scope} \begin{scope}[xshift=6cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (N) {$N$};
\node[rv, above of=Y, yshift=-0.3cm] (G) {$G$};
\draw[<->, dashed, thick] (N) -- (X);
\draw[<->, dashed, thick] (N) -- (Y);
\draw[<->, dashed, thick] (G) -- (X);
\draw[<->, dashed, thick] (G) -- (Y);
\draw[<->, dashed, thick] (N) -- (G);
\end{scope} \begin{scope}[xshift=9cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (O) {$O$};
\node[rv, above of=Y, yshift=-0.3cm] (G) {$G$};
\draw[<->, dashed, thick] (O) -- (X);
\draw[<->, dashed, thick] (O) -- (Y);
\draw[<->, dashed, thick] (G) -- (X);
\draw[<->, dashed, thick] (G) -- (Y);
\draw[<->, dashed, thick] (O) -- (G);
\end{scope} \end{tikzpicture} \\
\begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (N) {$N$};
\node[rv, above of=Y, yshift=-0.3cm] (D) {$D$};
\draw[<->, dashed, thick] (N) -- (X);
\draw[<->, dashed, thick] (N) -- (Y);
\draw[<->, dashed, thick] (D) -- (X);
\draw[<->, dashed, thick] (D) -- (Y);
\draw[<->, dashed, thick] (N) -- (D);
\end{scope} \begin{scope}[xshift=3cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (N) {$N$};
\node[rv, above of=Y, yshift=-0.3cm] (W) {$W$};
\draw[<->, dashed, thick] (N) -- (X);
\draw[<->, dashed, thick] (N) -- (Y);
\draw[<->, dashed, thick] (W) -- (X);
\draw[<->, dashed, thick] (W) -- (Y);
\draw[<->, dashed, thick] (N) -- (W);
\end{scope} \begin{scope}[xshift=6cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (N) {$N$};
\node[rv, above of=Y, yshift=-0.3cm] (E) {$E$};
\draw[<->, dashed, thick] (N) -- (X);
\draw[<->, dashed, thick] (N) -- (Y);
\draw[<->, dashed, thick] (E) -- (X);
\draw[<->, dashed, thick] (E) -- (Y);
\draw[<->, dashed, thick] (N) -- (E);
\end{scope} \begin{scope}[xshift=9cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\draw[<->, thick, color=blue] (X) -- (Y);
\end{scope} \end{tikzpicture}
\;\biggr], \quad \mathcal{R}=\left\{ \{O,F\} \right\}.
\end{multline*}

* Noting that $X \noconfpath T \mid F$, we immediately have

\begin{multline*}
\mathcal{Q} = \biggl[\; \boxed{\begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (T) {$T$};
\node[rv, above of=Y, yshift=-0.3cm] (F) {$F$};
\draw[<->, dashed, thick] (T) -- (Y);
\draw[<->, dashed, thick] (T) -- (F);
\draw[<->, dashed, thick] (F) -- (Y);
\end{scope} \end{tikzpicture}}^{\,\color{red} 0} \quad \begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, above of=X, yshift=-0.6cm, xshift=0.8cm] (F) {$F$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\draw[<->, thick, color=blue] (F) -- (X);
\draw[<->,dashed, thick] (F) -- (Y);
\end{scope} \begin{scope}[xshift=3cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (T) {$T$};
\node[rv, above of=Y, yshift=-0.3cm] (G) {$G$};
\draw[<->, dashed, thick] (T) -- (X);
\draw[<->, dashed, thick] (T) -- (Y);
\draw[<->, dashed, thick] (G) -- (X);
\draw[<->, dashed, thick] (G) -- (Y);
\draw[<->, dashed, thick] (T) -- (G);
\end{scope} \begin{scope}[xshift=6cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (N) {$N$};
\node[rv, above of=Y, yshift=-0.3cm] (G) {$G$};
\draw[<->, dashed, thick] (N) -- (X);
\draw[<->, dashed, thick] (N) -- (Y);
\draw[<->, dashed, thick] (G) -- (X);
\draw[<->, dashed, thick] (G) -- (Y);
\draw[<->, dashed, thick] (N) -- (G);
\end{scope} \begin{scope}[xshift=9cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (O) {$O$};
\node[rv, above of=Y, yshift=-0.3cm] (G) {$G$};
\draw[<->, dashed, thick] (O) -- (X);
\draw[<->, dashed, thick] (O) -- (Y);
\draw[<->, dashed, thick] (G) -- (X);
\draw[<->, dashed, thick] (G) -- (Y);
\draw[<->, dashed, thick] (O) -- (G);
\end{scope} \end{tikzpicture} \\
\begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (N) {$N$};
\node[rv, above of=Y, yshift=-0.3cm] (D) {$D$};
\draw[<->, dashed, thick] (N) -- (X);
\draw[<->, dashed, thick] (N) -- (Y);
\draw[<->, dashed, thick] (D) -- (X);
\draw[<->, dashed, thick] (D) -- (Y);
\draw[<->, dashed, thick] (N) -- (D);
\end{scope} \begin{scope}[xshift=3cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (N) {$N$};
\node[rv, above of=Y, yshift=-0.3cm] (W) {$W$};
\draw[<->, dashed, thick] (N) -- (X);
\draw[<->, dashed, thick] (N) -- (Y);
\draw[<->, dashed, thick] (W) -- (X);
\draw[<->, dashed, thick] (W) -- (Y);
\draw[<->, dashed, thick] (N) -- (W);
\end{scope} \begin{scope}[xshift=6cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (N) {$N$};
\node[rv, above of=Y, yshift=-0.3cm] (E) {$E$};
\draw[<->, dashed, thick] (N) -- (X);
\draw[<->, dashed, thick] (N) -- (Y);
\draw[<->, dashed, thick] (E) -- (X);
\draw[<->, dashed, thick] (E) -- (Y);
\draw[<->, dashed, thick] (N) -- (E);
\end{scope} \begin{scope}[xshift=9cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\draw[<->, thick, color=blue] (X) -- (Y);
\end{scope} \end{tikzpicture}
\;\biggr], \quad \mathcal{R}=\left\{\{O,F\}\right\}.
\end{multline*}

* Given that $X \diffdist Y$ in the boxed graph, we find another sufficient adjustment set $\{T,F\}$. We now have

\begin{multline*}
\mathcal{Q} = \biggl[\; \boxed{\begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, above of=X, yshift=-0.6cm, xshift=0.8cm] (F) {$F$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\draw[<->, thick, color=blue] (F) -- (X);
\draw[<->,dashed, thick, color=red] (F) -- (Y);
\end{scope} \end{tikzpicture}}^{\,\color{red} 1} \quad \begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (T) {$T$};
\node[rv, above of=Y, yshift=-0.3cm] (G) {$G$};
\draw[<->, dashed, thick] (T) -- (X);
\draw[<->, dashed, thick] (T) -- (Y);
\draw[<->, dashed, thick] (G) -- (X);
\draw[<->, dashed, thick] (G) -- (Y);
\draw[<->, dashed, thick] (T) -- (G);
\end{scope} \begin{scope}[xshift=3cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (N) {$N$};
\node[rv, above of=Y, yshift=-0.3cm] (G) {$G$};
\draw[<->, dashed, thick] (N) -- (X);
\draw[<->, dashed, thick] (N) -- (Y);
\draw[<->, dashed, thick] (G) -- (X);
\draw[<->, dashed, thick] (G) -- (Y);
\draw[<->, dashed, thick] (N) -- (G);
\end{scope} \begin{scope}[xshift=6cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (O) {$O$};
\node[rv, above of=Y, yshift=-0.3cm] (G) {$G$};
\draw[<->, dashed, thick] (O) -- (X);
\draw[<->, dashed, thick] (O) -- (Y);
\draw[<->, dashed, thick] (G) -- (X);
\draw[<->, dashed, thick] (G) -- (Y);
\draw[<->, dashed, thick] (O) -- (G);
\end{scope} \begin{scope}[xshift=9cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (N) {$N$};
\node[rv, above of=Y, yshift=-0.3cm] (D) {$D$};
\draw[<->, dashed, thick] (N) -- (X);
\draw[<->, dashed, thick] (N) -- (Y);
\draw[<->, dashed, thick] (D) -- (X);
\draw[<->, dashed, thick] (D) -- (Y);
\draw[<->, dashed, thick] (N) -- (D);
\end{scope} \end{tikzpicture} \\
\begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (N) {$N$};
\node[rv, above of=Y, yshift=-0.3cm] (W) {$W$};
\draw[<->, dashed, thick] (N) -- (X);
\draw[<->, dashed, thick] (N) -- (Y);
\draw[<->, dashed, thick] (W) -- (X);
\draw[<->, dashed, thick] (W) -- (Y);
\draw[<->, dashed, thick] (N) -- (W);
\end{scope} \begin{scope}[xshift=3cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (N) {$N$};
\node[rv, above of=Y, yshift=-0.3cm] (E) {$E$};
\draw[<->, dashed, thick] (N) -- (X);
\draw[<->, dashed, thick] (N) -- (Y);
\draw[<->, dashed, thick] (E) -- (X);
\draw[<->, dashed, thick] (E) -- (Y);
\draw[<->, dashed, thick] (N) -- (E);
\end{scope} \begin{scope}[xshift=6cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\draw[<->, thick, color=blue] (X) -- (Y);
\end{scope} \end{tikzpicture}
\;\biggr], \quad \mathcal{R}=\left\{ \{O,F\},\; {\color{blue} \{T,F\}} \right\}.
\end{multline*}

Besides $\{O,F\}$ and $\{T,F\}$, the algorithm will proceed to find all the other minimal sufficient adjustment sets: $\{O,G\}$, $\{D,N\}$, $\{E,F\}$, $\{N,W\}$ and $\{G,T\}$.  Due to space limit, we leave the rest to the reader.

§ DISCUSSION

We have shown that confounder selection, reformulated as blocking
confounding paths $X \confpath Y$, can be reduced to iteratively
finding primary adjustment sets that block confounding arcs $A
\confarc B$, where $(A,B)$ is either $(X,Y)$ or another pairs of variables
introduced in this process. Finding primary adjustment sets can
be further reduced to finding common causes and finding mediators.
The graph expansion procedure presented as <ref> provides
a systematic approach to confounder selection. In practice, the user or domain expert
interacts with the procedure by providing information to the subroutine in <ref>.
At least in principle, the information can be elicited by asking the following questions for various choices of variables $A,B$ and set $S$.

* Is there a common cause $C$ of $A$ and $B$ such that neither its effect on $A$ nor its effect on $B$ is fully mediated by $S$?

* If the answer is “yes”, is $C$ observed?

* If the answer to the first question is “yes” but to the second question is “no”, then what are some of the observed variables that, when combined with those variables already in $S$, fully
mediate the causal effect of $C$ on $A$ or the causal effect of $C$ on

Clearly, answering these questions does not require one's familiarity with causal graphs beyond the basic concepts of causes and mediators.

We conclude our paper with several remarks. First, it is evident that
graph expansion only requires partial knowledge about the underlying
graph. In particular, the procedure never inquires about the directed edges
between the variables in the working graph. Second, by construction
our method guards against the so-called collider bias or M-bias
[Greenland et al., 1999]. More broadly, the district criterion can
be employed to identify such bias for any given adjustment
set. Finally, we would like to stress again that confounder selection
is crucial for both the design and the analysis of an
observational study. As pointed out by Rubin, 2008,
“for objective causal
inference, design trumps analysis”. Building on the success of causal graphs to
represent structural assumptions, more work on
using causal graphs to aid the design of observational studies is much needed.

[Evans, 2018]
Robin J. Evans.
Markov properties for mixed graphical models.
In Handbook of Graphical Models, pages 39–60. CRC Press,

[Evans and Richardson, 2014]
Robin J. Evans and Thomas S. Richardson.
Markovian acyclic directed mixed graphs for discrete data.
The Annals of Statistics, 420 (4):0 1452 –
1482, 2014.

[Greenland and Robins, 2009]
Sander Greenland and James M. Robins.
Identifiability, exchangeability and confounding revisited.
Epidemiologic Perspectives & Innovations, 60
(1):0 1–9, 2009.

[Greenland et al., 1999]
Sander Greenland, Judea Pearl, and James M. Robins.
Causal diagrams for epidemiologic research.
Epidemiology, 100 (1):0 37–48, 1999.

[Guo et al., 2022]
F. Richard Guo, Anton Rask Lundborg, and Qingyuan Zhao.
Confounder selection: Objectives and approaches.
arXiv preprint arXiv:2208.13871, 2022.

[Haber et al., 2022]
Noah A Haber, Mollie E Wood, Sarah Wieten, and Alexander Breskin.
DAG with omitted objects displayed (DAGWOOD): a framework for
revealing causal assumptions in DAGs.
Annals of Epidemiology, 68:0 64–71, 2022.

[Henckel et al., 2022]
Leonard Henckel, Emilija Perković, and Marloes H. Maathuis.
Graphical criteria for efficient total effect estimation via
adjustment in causal linear models.
Journal of the Royal Statistical Society: Series B (Statistical
Methodology), 840 (2):0 579–599, 2022.

[Hernán and Robins, 2020]
Miguel A. Hernán and James M. Robins.
Causal Inference: What If.
Chapman & Hall/CRC, Boca Raton, 2020.

[Pearl, 1988]
Judea Pearl.
Probabilistic Reasoning in Intelligent Systems: Networks of
Plausible Inference.
Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1988.
ISBN 1558604790.

[Pearl, 1993]
Judea Pearl.
Comment: graphical models, causality and intervention.
Statistical Science, 80 (3):0 266–269, 1993.

[Pearl, 2009]
Judea Pearl.
Causality: Models, Reasoning, and Inference.
Cambridge University Press, 2nd edition, 2009.

[Pearl and Verma, 1991]
Judea Pearl and Thomas Verma.
A theory of inferred causation.
In Proceedings of the Second International Conference on
Principles of Knowledge Representation and Reasoning, KR'91,
pages 441–452, San Francisco, CA, USA, 1991. Morgan Kaufmann Publishers

[Richardson, 2003]
Thomas S. Richardson.
Markov properties for acyclic directed mixed graphs.
Scandinavian Journal of Statistics, 300 (1):0
145–157, 2003.

[Richardson and Robins, 2013]
Thomas S. Richardson and James M. Robins.
Single world intervention graphs (SWIGs): A unification of
the counterfactual and graphical approaches to causality.
Technical Report 128, Center for the Statistics and the Social
Sciences, University of Washington Series, 2013.

[Richardson et al., 2018]
Thomas S. Richardson, James M. Robins, and Linbo Wang.
Discussion of “Data-driven confounder selection via Markov and
Bayesian networks” by Häggström.
Biometrics, 740 (2):0 403–406, 2018.

[Richardson et al., 2023]
Thomas S. Richardson, Robin J. Evans, James M. Robins, and Ilya Shpitser.
Nested Markov properties for acyclic directed mixed graphs.
The Annals of Statistics, 510 (1):0 334–361,

[Rosenbaum and Rubin, 1983]
Paul R. Rosenbaum and Donald B. Rubin.
The central role of the propensity score in observational studies for
causal effects.
Biometrika, 700 (1):0 41–55, 1983.

[Rotnitzky and Smucler, 2020]
Andrea Rotnitzky and Ezequiel Smucler.
Efficient adjustment sets for population average causal treatment
effect estimation in graphical models.
Journal of Machine Learning Research, 210
(188):0 1–86, 2020.

[Rubin, 2008]
Donald B. Rubin.
For objective causal inference, design trumps analysis.
The Annals of Applied Statistics, 20 (3):0
808–840, 2008.

[Sadeghi and Lauritzen, 2014]
Kayvan Sadeghi and Steffen Lauritzen.
Markov properties for mixed graphs.
Bernoulli, 200 (2):0 676 – 696, 2014.

[Shpitser et al., 2010]
Ilya Shpitser, Tyler J. VanderWeele, and James M. Robins.
On the validity of covariate adjustment for estimating causal
In Proceedings of the Twenty-Sixth Conference on Uncertainty in
Artificial Intelligence, UAI'10, pages 527–536, Arlington, Virginia, USA,
2010. AUAI Press.

[Shpitser et al., 2022]
Ilya Shpitser, Thomas S. Richardson, and James M. Robins.
Multivariate Counterfactual Systems and Causal Graphical
Models, pages 813–852.
Association for Computing Machinery, New York, NY, USA, 2022.

[Shrier and Platt, 2008]
Ian Shrier and Robert W Platt.
Reducing bias through directed acyclic graphs.
BMC Medical Research Methodology, 8:0 1–15, 2008.

[Smucler and Rotnitzky, 2022]
Ezequiel Smucler and Andrea Rotnitzky.
A note on efficient minimum cost adjustment sets in causal graphical
Journal of Causal Inference, 100 (1):0
174–189, 2022.

[Spirtes et al., 1993]
Peter Spirtes, Clark Glymour, and Richard Scheines.
Causation, Prediction, and Search, volume 81 of
Lecture Notes in Statistics.
Springer, New York, NY, 1993.

[Sullivant et al., 2010]
Seth Sullivant, Kelli Talaska, and Jan Draisma.
Trek separation for Gaussian graphical models.
The Annals of Statistics, 380 (3):0
1665–1685, 2010.

[van der Zander et al., 2019]
Benito van der Zander, Maciej Liśkiewicz, and Johannes Textor.
Separators and adjustment sets in causal graphs: Complete criteria
and an algorithmic framework.
Artificial Intelligence, 270:0 1–40, 2019.

[VanderWeele, 2019]
Tyler J. VanderWeele.
Principles of confounder selection.
European Journal of Epidemiology, 340 (3):0
211–219, 2019.

[VanderWeele and Shpitser, 2011]
Tyler J. VanderWeele and Ilya Shpitser.
A new criterion for confounder selection.
Biometrics, 670 (4):0 1406–1413, 2011.

[VanderWeele and Shpitser, 2013]
Tyler J. VanderWeele and Ilya Shpitser.
On the definition of a confounder.
The Annals of Statistics, 410 (1):0 196–220,

[Verma and Pearl, 1990]
Thomas S Verma and Judea Pearl.
Equivalence and synthesis of causal models.
In Proceedings of the 6th Conference on Uncertainty in
Artificial Intelligence (UAI-1990), pages 220–227, Cambridge, MA, USA,

§ PROOFS

§.§ Proof of <ref>

Because the causal model with $X \notin \de(Y)$ is included by the causal model with $X \in \an(Y)$, the first statement is implied by the second statement. We only need to show the second statement. Pearl's back-door criterion can be stated as (i) $S \cap \de(X) = \emptyset$ and (ii) $X \leftrightsquigarrow \,\centernot{\ast}\, \fullsquighalf Y \mid S$. Given $X \in \an(Y)$, it follows that $\text{(i)} \iff S \cap (\de(X) \cup \de(Y)) = \emptyset$. Clearly, $\text{(ii)} \implies A \noconfpath B \mid S$ and it remains to show that the reverse is also true. To prove by contradiction, suppose $A \noconfpath B \mid S$ but $X \leftrightsquigarrow \ast \fullsquighalf Y \mid S$, from which we have $X \leftrightsquigarrow \ast \fullsquigno Y \mid S$. By $X \in \an(Y)$ and acyclicity, such an m-connected path must have colliders. Let $C$ be the collider on the path that is closest to $Y$. Then, the m-connection implies $C \in \bar{\an}(S)$ and further $Y \in \an(S)$, contradicting (i).

§.§ Proof of <Ref>

`$\Rightarrow$' direction: By definition, $\sP_{\gG}(A \rightdirpath B \mid C)
\subseteq \sW^s_{\gG}(A \rightdirpath B \mid C)$ and $\sP_{\gG}(A \confarc B \mid C)
\subseteq \sW^s_{\gG}(A \confarc B \mid C)$ because there are no
colliders. We are left to show the last implication, i.e. the
existence of m-connected confounding paths implies the existence of
m$^{*}$-connected confounding simple walks.

Let $\tau \in \sP_{\gG}(A
\confpath B \mid C)$ and suppose, without loss of generality, $\tau$
contains a sequence of colliders $\tilde{C}_1, \dots, \tilde{C}_k$ with
$\tilde{C}_1$ closest to $A$ ($k \geq 1$). In other words, $\tau$
looks like

\[
A \confarc \tilde{C}_1 \confarc \dotsb \confarc \tilde{C}_k
\confarc B.
\]

We associate with each $\tilde{C}_i$ a vertex $C_i$. Because
$\tau$ is m-connected, we have $\tilde{C}_i \in \overline{\an}(C)$ for $i = 1,\dots,k$.
If $\tilde{C}_i \in C$, let $C_i = \tilde{C}_i$; otherwise, choose a vertex
$C_i \in C$ that is among the closest to $\tilde{C}_i$ by directed
edges and expand $\tau$ at $C_i$ as:

\begin{equation}
\label{eq:added-segment}
\dotsb \confarc \tilde{C}_i \rightsquigarrow C_i \leftsquigarrow
\tilde{C}_i \confarc \dotsb.
\end{equation}

By choosing the segments $\tilde{C}_i \rightsquigarrow C_i$ to be a
shortest directed path from $\tilde{C}_i$ to $C_i$ (and $C_i
\leftsquigarrow \tilde{C}_i$ to be its reverse), this introduces no
new vertices in $C$ other than $C_i$. Repeating this expansion for
every $i = 1,\dotsc,k$, we obtain a confounding walk, denoted as
$\pi_0$, that looks like

\[
A \confarc C_1 \confarc \dotsb \confarc C_k
\confarc B.
\]

This walk is m$^{*}$-connected given $C$, i.e. $\pi_0 \in \sW_{\gG}(A
\confpath B \mid C)$, because all of its colliders are in
$C$ and none of its non-colliders is in $C$.

However, $\pi_0$ is
not necessarily a simple walk because $A$ or $B$ may appear in an added
segment in (<ref>). Suppose $A$ appears in the
segment $\tilde{C}_i \rightsquigarrow C_i \leftsquigarrow
\tilde{C}_i$; clearly $A \neq C_i$ because $C_i
\in C$ but $A \not \in C$. Thus, the walk $\pi_0$ looks like

\[
A \confarc C_1 \confarc \dotsb \confarc \tilde{C}_i \rightsquigarrow A \rightsquigarrow C_i
\leftsquigarrow A \leftsquigarrow \tilde{C}_i \confarc \dotsb
\confarc C_k \confarc B.
\]

We may then “restart” the walk by considering the subwalk
starting from the last $A$ in the last display. Similarly, if $B$
appears in this segment and $\pi_0$ looks like

\[
A \confarc C_1 \confarc \dotsb \confarc \tilde{C}_i \rightsquigarrow B \rightsquigarrow C_i
\leftsquigarrow B \leftsquigarrow \tilde{C}_i \confarc \dotsb
\confarc C_k \confarc B,
\]

we may consider the sub-walk ending at the first $B$. By repeating
this operation, we arrive at a simple, m-connected walk $\pi$ with
both arrowheads at $A$ and $B$ preserved. In other words, $\pi \in
\sW^s_{\gG}(A \confpath B \mid C)$.

It is easy to see that, by the same expansion and deduplication
operations, we can construct a m$^{*}$-connected simple walk $\pi \in
\sW^s_{\gG}(A \mconn B \mid C)$ from a m-connected path $\tau \in
\sP_{\gG}(A \mconn B \mid C)$.

`$\Leftarrow$' direction: Consider $\pi \in \sW_{\gG}^s(A \rightdirpath B \mid
C)$. Because $\gG$ is acyclic, $\pi$ must contain no repeated
vertices so $\pi \in \sP_{\gG}(A \rightdirpath B \mid
C)$. Consider $\pi \in \sW_{\gG}^s(A \confarc B \mid C)$, so $\pi$
looks like

\[
A \leftdirpath U_1 \rightdirpath B \quad \text{or} \quad A
\leftdirpath U_1 \leftrightarrow U_2 \rightdirpath B.
\]

If $\pi$
contains repeated vertices, let $D$ be the repeated vertex closest
to $A$ in $\pi$. Because $\gG$ is acyclic, $D$ must appear exactly
once in the segement $A \leftdirpath U_1$ and exactly once in the
segment $U_1
\rightdirpath B$ or $U_2 \rightsquigarrow B$. In other words, $\pi$
looks like

\begin{align*}
&A \leftdirpath D \leftdirpath U_1 \rightdirpath D \rightdirpath B,
\quad A \leftdirpath D \leftrightarrow U_2 \rightdirpath D
\rightdirpath B, \\
&A \leftdirpath D \leftdirpath U_1
\leftrightarrow D \rightdirpath B, \quad  \text{or} \quad A
\leftdirpath D \leftdirpath U_1 \leftrightarrow U_2 \rightdirpath D
\rightdirpath B.
\end{align*}

In either case, we can obtain a m$^{*}$-connected walk $\tau$ that looks like $A \leftdirpath D \rightdirpath B$ by concatenating the first and last
segments of the walk. Because $D$ is the closest repeated vertex to
$A$ in $\pi$, this new walk has no repeated vertices, i.e. $\tau \in
\sP_{\gG}(A \confarc B \mid C)$.

Now consider $\pi \in \sW_{\gG}^s(A \confpath B \mid C)$. Suppose a
vertex $D$ appears more than once in $\pi$. Because $\pi$ is simple,
we know $D \not \in \{A, B\}$. Motivated by the above
argument for confounding arcs, consider the following deduplication
operation. For any simple walk $\lambda$ from $A$ to $B$ with a repated
vertex $D$, let $\lambda'$ be the concatenation of the sub-walk from
$A$ to the first occurrence of $D$ and the subwalk from the last
occurrence of $D$ to $B$. To visualize this, $\lambda$ can always be
represented as

\[
A \halfsquigfull \ast \fullsquighalf D \mconn D \halfsquigfull \ast
\fullsquighalf B.
\]

The deduplicated walk $\lambda'$ then looks like

\[
A \halfsquigfull \ast \fullsquighalf D \halfsquigfull \ast
\fullsquighalf B.
\]

Suppose that $\lambda$ satisfies the following two properties:

\begin{align*}
\text{(P1) }& \text{all occurrences of the same vertex are of the
same type, i.e., a collider or a non-collider},\\
\text{(P2) }& \text{all non-colliders are not in $C$ and all
colliders are contained in $\overline{\an}(C)$}.
\end{align*}

Then, we claim that the map $\lambda \mapsto \lambda'$ preserves these properties.
To show this, consider the following two cases.

* $D$ is a collider on $\lambda$, so $\lambda$ looks like

\[
A \halfsquigfull \ast \fullsquigfull D \confpath D \fullsquigfull
\ast
\fullsquighalf B.
\]

It is obvious that $D$ is also a collider on
$\lambda'$. Because $\lambda$ satisfies (P1), we have $D \in
\overline{\an}(C)$. It is easy to see that $\lambda'$ satisfies

* $D$ is not a collider on $\lambda$. If $D$ is also a
non-collider on $\lambda'$, clearly (P1–2) hold for
$\lambda'$. If $D$ becomes a new collider on $\lambda'$, then
$\lambda$ looks like

\[
A \halfsquigfull \ast \fullsquigfull D \nosquigfull \ast
\fullsquigno D \fullsquigfull \ast \fullsquighalf B.
\]

Observe that on $\lambda$ there exists one or more colliders
between the first and last occurrence of $D$, and $\lambda$
contains a directed path from $D$ to a collider. This implies that
$D \in \overline{\an}(C)$. Thus, (P1–2) continue to hold for

We now return to the simple, confounding walk $\pi \in \sW_{\gG}^s(A
\confpath B \mid C)$. Let $\pi'$ denote the image
of $\pi$ under the deduplicating operation above. Because $\pi$ is
m$^{*}$-connected given $C$, it is obvious that $\pi$ satisfies
(P1–2). Thus, $\pi'$ also satisfies (P1-P2). By iteratively
applying the deduplication, we eventually eliminate all repeated
vertices on $\pi$ and arrive at a path $\tau$ from $A$ to $B$ that
satisfies (P1–2). It immediately follows from (P2) that $\tau$ is
m-connected given $C$. Moreover, both endpoint arrowheads of $\pi$
are preserved by the deduplication above. Thus, $\tau \in \sP_{\gG}(A
\confpath B \mid C)$.

It is easy to see that we can use the same deduplication process to
construct a m-connected path $\tau \in
\sP_{\gG}(A \mconn B \mid C)$ from a m$^{*}$-connected simple walk $\pi \in
\sW^s_{\gG}(A \mconn B \mid C)$. This completes our proof.

§.§ Proof of <Ref>

We first consider the preservation from $\gG$ to $\gG(\tilde{V})$.
Let $\pi \in \sW_{\gG}^s(A
\mconn B \mid C)$. Its latent projection onto $\tilde{V}$ is a walk $\pi'$
in $\gG(\tilde{V})$ defined as follows. Let $D_0 = A, D_1, \dots, D_k,
D_{k+1} = B$ ($k \geq 0$) be all vertices on $\pi$ that are
contained in $\tilde{V}$. By denoting $U = V \setminus \tilde{V}$, $\pi$ looks like

\begin{equation}
\label{eq:pi-before-proj}
A = D_0 \overset{\text{via}\,U}{\mconnarc} D_1
\overset{\text{via}\,U}{\mconnarc} \dotsb
\overset{\text{via}\,U}{\mconnarc} D_k
\overset{\text{via}\,U}{\mconnarc} D_{k+1} = B,
\end{equation}

where between every $(D_i, D_{i+1})$ there is a m$^{*}$-connected arc because $U \cap C = \emptyset$. The latent projection of each arc $D_i
\overset{\text{via}\,U}{\mconnarc} D_{i+1}$ on $\tilde{V} = V \setminus U$
is defined as

\[
\begin{Bmatrix}
\overset{\text{via}\,U}{\rightdirpath} \\
\overset{\text{via}\,U}{\leftdirpath} \\
\overset{\text{via}\,U}{\fullsquigfull} \\
\end{Bmatrix}
\quad
\mapsto
\quad
\begin{Bmatrix}
\rightarrow \\
\leftarrow \\
\leftrightarrow \\
\end{Bmatrix}
\]

where the corresponding edge on the RHS must exist in $\gG(\tilde{V})$ by the definition of
latent projection.
Thus, the latent projection of $\pi$ is a simple walk $\pi'$ in
$\gG(\tilde{V})$ that looks like

\begin{equation}
\label{eq:pi-after-proj}
A = D_0 \halfstraighalf D_1 \halfstraighalf \dotsb \halfstraighalf
D_k \halfstraighalf D_{k+1} = B.
\end{equation}

Thus, we conclude that $\pi' \in \sW_{\gG(\tilde{V})}^s(A \mconn B \mid C)$.
Further, because the latent projection as defined above preserves endpoint
arrowheads, $D_i$ is a collider on $\pi'$ if and only if $D_i$ is a
collider on $\pi$. Consequently, we also have

\[
\pi \in \sW_{\gG}^s \left( A \begin{Bmatrix} \rightdirpath \\ \confarc \\
\confpath \end{Bmatrix} B \mid C  \right) \quad
\implies \quad
\pi' \in \sW_{\gG(\tilde{V})}^s \left( A \begin{Bmatrix} \rightdirpath \\ \confarc \\
\confpath \end{Bmatrix} B \mid C  \right).
\]

Now we prove the reverse direction.
Given any $\pi' \in \sW_{\gG(\tilde{V})}^s(A \mconn B \mid C)$, we want to find a
simple, m-connected walk $\pi$ in $\gG$. Walk $\pi'$ can be written as
(<ref>) for some $A = D_0, D_1,\dots,D_k, D_{k+1}=B
\in \tilde{V}$. By reverting the latent projection, we obtain a walk $\pi$ in
$\gG$ that looks like (<ref>). It is easy to see
that $\pi$ is simple because $A,B \not \in U$ and $A, B \not
\in \{D_1,\dots,D_k\}$ since the $\pi'$ is simple. Further, because
each segment between $D_i$ and $D_{i+1}$ is an arc and contains no
collider, $\pi$ and $\pi'$ have the same set of colliders. Therefore,
we conclude that $\pi \in \sW_{\gG}^s(A \mconn B \mid C)$. Further, by
the fact that $\pi$ and $\pi$ have the same endpoint arrowheads/tails and the
same set of colliders, we also have

\[ \pi' \in \sW_{\gG(\tilde{V})}^s \left( A \begin{Bmatrix} \rightdirpath \\ \confarc \\
\confpath \end{Bmatrix} B \mid C  \right) \quad
\implies \quad
\pi \in \sW_{\gG}^s \left( A \begin{Bmatrix} \rightdirpath \\ \confarc \\
\confpath \end{Bmatrix} B \mid C  \right).\]

§.§ Proof of <ref>

Properties (i)–(iii) and (vii) directly follow from definition.

We claim that $\mathcal{J}_{\noconfarc}$ satisfies (iv) weak union. By (iii), $A \noconfarc B, C \mid D$ implies $A \noconfarc B \mid D$, which leads to $A \noconfarc B \mid C, D$ by <ref>.

We claim that $\mathcal{J}_{\noconfpath}$  also satisfies (iv) weak union. We show its contraposition $A \confpath B \mid C, D \implies A \confpath B, C \mid D$. From $A \confpath B \mid C, D$, we have $a \confarc b \mid C, D$ for some $a \in A$ and some $b \in B$ in $\gG$. Let $\tilde{\gG} := \gG(\{a,b\} \cup C \cup D)$. By <ref>, we have $a \samedist b \mid C, D$ in $\tilde{\gG}$. Let $\pi: a=v_0 \leftrightarrow \dots \leftrightarrow v_{k+1} = b$ with $k \geq 0$ be any $\samedist$ path between $a$ and $b$ in $\tilde{\gG}$ that is m-connected given $C, D$. If $k=0$, we have $a \leftrightarrow b \mid C, D$ in $\tilde{\gG}$, which by <ref> implies $a \confarc b \mid C, D$ in $\gG$. It further follows from <ref> that $a \confarc b \mid D$ in $\gG$ and hence $A \confpath B \mid D$ in $\gG$.
Now we suppose $k \geq 1$. By definition of $\tilde{\gG}$, we have $v_1, \dots, v_k \in C \cup D$. If $v_1, \dots, v_k \in D$, then we have $a \samedist b \mid D$ and hence $a \confpath b \mid D$ in $\tilde{\gG}$. By <ref>, it follows that $a \confpath b \mid D$ in $\gG$ and hence $A \confpath B \mid D$ in $\gG$.
Otherwise, let $1 \leq k' \leq k$ be the first vertex such that $v_{k'} \in C$. Observing that $a \leftrightarrow \dots \leftrightarrow v_{k'}$ is m-connected given $D$, we have $a \samedist v_{k'} \mid D$ in $\tilde{\gG}$ and hence $a \confpath v_{k'} \mid D$ in $\tilde{\gG}$. By <ref>, it follows that $A \confpath C \mid D$ in $\gG$.

We show that $\mathcal{J}_{\noconfpath}$ does not satisfy (v) contraction or (vi) intersection on some ADMG. Consider the simple example $A \leftarrow C \rightarrow B$ and let $D = \emptyset$. Given $A \noconfpath C \mid \emptyset$ and $A \noconfpath B \mid C$, (v) contraction would imply $A \noconfpath B,C \mid \emptyset$, which fails here. Also, given $A \noconfpath B \mid C$ and $A \noconfpath C \mid B$, (vi) intersection would imply $A \noconfpath B,C \mid \emptyset$, which again fails. Similarly, because $\mathcal{J}_{\noconfpath}$ implies $\mathcal{J}_{\noconfarc}$, (v) contraction or (vi) intersection for $\mathcal{J}_{\noconfarc}$ would imply $A \noconfarc B,C \mid \emptyset$, which fails. Hence, relation $\mathcal{J}_{\noconfarc}$ also fails to satisfy (v) and (vi).

§ RECURSIVE VERSION OF THE GRAPH EXPANSION ALGORITHM

The recursive version of the graph expansion algorithm is shorter but
less flexible. See <Ref>.

Confounder selection via graph expansion (recursive version)

[1] ConfounderSelect$X$, $Y$
$\mathcal{R} = \emptyset$
GraphExpand$S$, $\mathcal{B}_y$, $\mathcal{B}_n$
$\bar{S} = S \cup X \cup Y$
$X \samedist Y$ by edges in
$X \diffdist Y$ by edges in $(\bar{S}
\times \bar{S}) \setminus \mathcal{B}_n$
$\mathcal{R} = \mathcal{R} \cup \{S\}$
$(A,B) = \pi = $ SelectEdge$X$, $Y$, $S$, $\mathcal{B}_y$, $\mathcal{B}_n$
$\mathcal{L} = $ FindPrimary$(A,B); S \setminus \{A,B\}$
$C$ in FindPrimary$\pi$, $S \setminus \{A, B\}$
Primary adjustment sets for $\pi$ given $S$
GraphExpand$S \cup C$, $\mathcal{B}_y$,
$\mathcal{B}_{n} \cup \{\pi\}$
GraphExpand$S$, $\mathcal{B}_y \cup \{\pi\}$,
GraphExpand$\emptyset$, $\emptyset$,
Initial graph has a possible edge $X \leftrightarrow Y$

§ EXAMPLE WITH UNOBSERVED VARIABLES

We illustrate <ref> with another ADMG in
<Ref>, where $U_1$ and $U_2$ are
unobserved. For this case, $\{B,D\}$ is the only minimal adjustment
set. We use $\color{blue} \barrow$ to draw those edges in
$\mathcal{B}_y$ that are no longer expanded and use $\dbarrow$ to draw
those edges in $(\bar{S} \times \bar{S}) \setminus (\mathcal{B}_y \cup
\mathcal{B}_n)$ that can be further expanded. The min-cut strategy in
<ref> is adopted. The graph popped from the
queue is drawn with a box with its min-cut index marked in the upper
right corner. The edge $\pi$ chosen by SelectEdge is
highlighted with $\color{red} \dbarrow$. Suppose subroutine
FindPrimary returns all the minimal primary adjustment sets
(i.e., with option ),
so that the algorithm is guaranteed to find $\{B,D\}$ by

rv/.style=circle,inner sep=1pt,draw,font=,
lv/.style=circle,inner sep=1pt,fill=gray!20,draw,font=,
fv/.style=rectangle,inner sep=1.5pt,fill=gray!20,draw,font=,
node distance=12mm, >=stealth
[rv] (X) $X$;
[rv, right of=X, xshift=0.5cm] (Y) $Y$;
[rv, above of=X, yshift=-0.6cm, xshift=0.8cm] (B) $B$;
[rv, above of=X] (D) $D$;
[rv, above of=Y] (C) $C$;
[lv, above of=D, xshift=8mm, yshift=-4mm] (U1) $U_1$;
[lv, right of=B, xshift=5mm] (U2) $U_2$;
[->, thick] (X) – (Y);
[->, thick] (B) – (X);
[->, thick] (B) – (Y);
[->, thick] (D) – (B);
[->, thick] (D) – (X);
[->, thick] (C) – (B);
[->, thick] (C) – (D);
[->, thick] (U1) – (D);
[->, thick] (U1) – (C);
[->, thick] (U2) – (C);
[->, thick] (U2) – (Y);
[->, thick] (C) – (Y);

Variables $U_1, U_2$ are unobserved.

* We start with

\[  \mathcal{Q} = \biggl[\; \boxed{\begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\draw[<->, dashed, thick, color=red] (X) -- (Y);
\end{tikzpicture}}^{\,\color{red} 1} \; \biggr], \quad \mathcal{R}=\{\}. \]

* We have $\textsc{FindPrimary}((X,Y); \emptyset, \texttt{True}) = \left\{\{B,C\}, \{B,D\} \right\}$ and

\[\mathcal{Q} = \biggl[\; \boxed{\begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (B) {$B$};
\node[rv, above of=Y, yshift=-0.3cm] (C) {$C$};
\draw[<->, dashed, thick, color=red] (B) -- (X);
\draw[<->, dashed, thick] (B) -- (Y);
\draw[<->, dashed, thick] (C) -- (X);
\draw[<->, dashed, thick] (C) -- (Y);
\draw[<->, dashed, thick] (B) -- (C);
\end{scope} \end{tikzpicture}}^{\,\color{red} 2} \qquad \begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (B) {$B$};
\node[rv, above of=Y, yshift=-0.3cm] (D) {$D$};
\draw[<->, dashed, thick] (B) -- (X);
\draw[<->, dashed, thick] (B) -- (Y);
\draw[<->, dashed, thick] (D) -- (X);
\draw[<->, dashed, thick] (D) -- (Y);
\draw[<->, dashed, thick] (B) -- (D);
\end{scope} \begin{scope}[xshift=3cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\draw[<->, thick, color=blue] (X) -- (Y);
\end{scope} \end{tikzpicture}
\;\biggr], \quad \mathcal{R}=\{\}.\]

* In light of $\textsc{FindPrimary}((B,X); \{C\}, \texttt{True}) = \left\{\{D\}
\right\}$, we have

\[\mathcal{Q} = \biggl[\; \boxed{\begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (B) {$B$};
\node[rv, above of=Y, yshift=-0.3cm] (C) {$C$};
\node[rv, above of=B, xshift=0.8cm, yshift=-0.3cm] (D) {$D$};
\draw[<->, dashed, thick] (B) -- (Y);
\draw[<->, dashed, thick] (C) -- (X);
\draw[<->, dashed, thick] (C) -- (Y);
\draw[<->, dashed, thick] (B) -- (C);
\draw[<->, dashed, thick, color=red] (D) -- (X);
\draw[<->, dashed, thick] (D) -- (Y);
\draw[<->, dashed, thick] (D) -- (B);
\draw[<->, dashed, thick] (D) -- (C);
\end{scope} \end{tikzpicture}}^{\,\color{red} 2} \qquad \begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (B) {$B$};
\node[rv, above of=Y, yshift=-0.3cm] (C) {$C$};
\draw[<->, thick, color=blue] (B) -- (X);
\draw[<->, dashed, thick] (B) -- (Y);
\draw[<->, dashed, thick] (C) -- (X);
\draw[<->, dashed, thick] (C) -- (Y);
\draw[<->, dashed, thick] (B) -- (C);
\end{scope} \begin{scope}[xshift=3cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (B) {$B$};
\node[rv, above of=Y, yshift=-0.3cm] (D) {$D$};
\draw[<->, dashed, thick] (B) -- (X);
\draw[<->, dashed, thick] (B) -- (Y);
\draw[<->, dashed, thick] (D) -- (X);
\draw[<->, dashed, thick] (D) -- (Y);
\draw[<->, dashed, thick] (B) -- (D);
\end{scope} \begin{scope}[xshift=6cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\draw[<->, thick, color=blue] (X) -- (Y);
\end{scope} \end{tikzpicture}
\;\biggr], \quad \mathcal{R}=\{\}.\]

\[\mathcal{Q} = \biggl[\; \boxed{\begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (B) {$B$};
\node[rv, above of=Y, yshift=-0.3cm] (C) {$C$};
\node[rv, above of=B, xshift=0.8cm, yshift=-0.3cm] (D) {$D$};
\draw[<->, dashed, thick] (B) -- (Y);
\draw[<->, dashed, thick, color=red] (C) -- (X);
\draw[<->, dashed, thick] (C) -- (Y);
\draw[<->, dashed, thick] (B) -- (C);
\draw[<->, dashed, thick] (D) -- (Y);
\draw[<->, dashed, thick] (D) -- (B);
\draw[<->, dashed, thick] (D) -- (C);
\end{scope} \end{tikzpicture}}^{\,\color{red} 1} \qquad \begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (B) {$B$};
\node[rv, above of=Y, yshift=-0.3cm] (C) {$C$};
\draw[<->, thick, color=blue] (B) -- (X);
\draw[<->, dashed, thick] (B) -- (Y);
\draw[<->, dashed, thick] (C) -- (X);
\draw[<->, dashed, thick] (C) -- (Y);
\draw[<->, dashed, thick] (B) -- (C);
\end{scope} \begin{scope}[xshift=3cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (B) {$B$};
\node[rv, above of=Y, yshift=-0.3cm] (D) {$D$};
\draw[<->, dashed, thick] (B) -- (X);
\draw[<->, dashed, thick] (B) -- (Y);
\draw[<->, dashed, thick] (D) -- (X);
\draw[<->, dashed, thick] (D) -- (Y);
\draw[<->, dashed, thick] (B) -- (D);
\end{scope} \begin{scope}[xshift=6cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\draw[<->, thick, color=blue] (X) -- (Y);
\end{scope} \end{tikzpicture}
\;\biggr], \quad \mathcal{R}=\{\}.\]

\[\mathcal{Q} = \biggl[\; \boxed{\begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (B) {$B$};
\node[rv, above of=Y, yshift=-0.3cm] (C) {$C$};
\node[rv, above of=B, xshift=0.8cm, yshift=-0.3cm] (D) {$D$};
\draw[<->, dashed, thick] (B) -- (Y);
\draw[<->, dashed, thick] (C) -- (Y);
\draw[<->, dashed, thick] (B) -- (C);
\draw[<->, dashed, thick] (D) -- (Y);
\draw[<->, dashed, thick] (D) -- (B);
\draw[<->, dashed, thick] (D) -- (C);
\end{scope} \end{tikzpicture}}^{\,\color{red} 0} \qquad \begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (B) {$B$};
\node[rv, above of=Y, yshift=-0.3cm] (C) {$C$};
\draw[<->, thick, color=blue] (B) -- (X);
\draw[<->, dashed, thick] (B) -- (Y);
\draw[<->, dashed, thick] (C) -- (X);
\draw[<->, dashed, thick] (C) -- (Y);
\draw[<->, dashed, thick] (B) -- (C);
\end{scope} \begin{scope}[xshift=3cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (B) {$B$};
\node[rv, above of=Y, yshift=-0.3cm] (D) {$D$};
\draw[<->, dashed, thick] (B) -- (X);
\draw[<->, dashed, thick] (B) -- (Y);
\draw[<->, dashed, thick] (D) -- (X);
\draw[<->, dashed, thick] (D) -- (Y);
\draw[<->, dashed, thick] (B) -- (D);
\end{scope} \begin{scope}[xshift=6cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\draw[<->, thick, color=blue] (X) -- (Y);
\end{scope} \end{tikzpicture}
\;\biggr], \quad \mathcal{R}=\{\}.\]

\[\mathcal{Q} = \biggl[\; \boxed{\begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (B) {$B$};
\node[rv, above of=Y, yshift=-0.3cm] (C) {$C$};
\draw[<->, thick, color=blue] (B) -- (X);
\draw[<->, dashed, thick, color=red] (B) -- (Y);
\draw[<->, dashed, thick] (C) -- (X);
\draw[<->, dashed, thick] (C) -- (Y);
\draw[<->, dashed, thick] (B) -- (C);
\end{scope} \end{tikzpicture}}^{\,\color{red} 2} \qquad \begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (B) {$B$};
\node[rv, above of=Y, yshift=-0.3cm] (D) {$D$};
\draw[<->, dashed, thick] (B) -- (X);
\draw[<->, dashed, thick] (B) -- (Y);
\draw[<->, dashed, thick] (D) -- (X);
\draw[<->, dashed, thick] (D) -- (Y);
\draw[<->, dashed, thick] (B) -- (D);
\end{scope} \begin{scope}[xshift=3cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\draw[<->, thick, color=blue] (X) -- (Y);
\end{scope} \end{tikzpicture}
\;\biggr], \quad \mathcal{R}=\{{\color{blue} \{B,C,D \}}\}.\]

\[\mathcal{Q} = \biggl[\; \boxed{\begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (B) {$B$};
\node[rv, above of=Y, yshift=-0.3cm] (C) {$C$};
\draw[<->, thick, color=blue] (B) -- (X);
\draw[<->, dashed, thick] (C) -- (X);
\draw[<->, dashed, thick, color=red] (C) -- (Y);
\draw[<->, dashed, thick] (B) -- (C);
\end{scope} \end{tikzpicture}}^{\,\color{red} 1} \qquad \begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (B) {$B$};
\node[rv, above of=Y, yshift=-0.3cm] (D) {$D$};
\draw[<->, dashed, thick] (B) -- (X);
\draw[<->, dashed, thick] (B) -- (Y);
\draw[<->, dashed, thick] (D) -- (X);
\draw[<->, dashed, thick] (D) -- (Y);
\draw[<->, dashed, thick] (B) -- (D);
\end{scope} \begin{scope}[xshift=3cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\draw[<->, thick, color=blue] (X) -- (Y);
\end{scope} \end{tikzpicture}
\;\biggr], \quad \mathcal{R}=\{\{B,C,D \}\}.\]

* Due to $C \leftarrow U_2 \rightarrow Y$, we have

\[\mathcal{Q} = \biggl[\; \boxed{\begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (B) {$B$};
\node[rv, above of=Y, yshift=-0.3cm] (C) {$C$};
\draw[<->, thick, color=blue] (B) -- (X);
\draw[<->, dashed, thick] (C) -- (X);
\draw[<->, thick, color=blue] (C) -- (Y);
\draw[<->, dashed, thick, color=red] (B) -- (C);
\end{scope} \end{tikzpicture}}^{\,\color{red} 2} \qquad \begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (B) {$B$};
\node[rv, above of=Y, yshift=-0.3cm] (D) {$D$};
\draw[<->, dashed, thick] (B) -- (X);
\draw[<->, dashed, thick] (B) -- (Y);
\draw[<->, dashed, thick] (D) -- (X);
\draw[<->, dashed, thick] (D) -- (Y);
\draw[<->, dashed, thick] (B) -- (D);
\end{scope} \begin{scope}[xshift=3cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\draw[<->, thick, color=blue] (X) -- (Y);
\end{scope} \end{tikzpicture}
\;\biggr], \quad \mathcal{R}=\{\{B,C,D \}\}.\]

* Because $\textsc{FindPrimary}((B,C); \emptyset, \texttt{True}) = \left\{\{D\} \right\}$, two graphs are added: (1) expanding $B {\color{red} \dbarrow} C$ by introducing $D$ and (2) turning $B {\color{red} \dbarrow} C$ to $B {\color{blue} \barrow} C$. However, because they have $\text{min-cut}=3$ and $\text{min-cut}=\infty$ respectively, they are not chosen next.

\[\mathcal{Q} = \biggl[\; \begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (B) {$B$};
\node[rv, above of=Y, yshift=-0.3cm] (C) {$C$};
\node[rv, above of=B, xshift=0.8cm, yshift=-0.3cm] (D) {$D$};
\draw[<->, thick, color=blue] (B) -- (X);
\draw[<->, dashed, thick] (C) -- (X);
\draw[<->, thick, color=blue] (C) -- (Y);
\draw[<->, dashed, thick] (D) -- (B);
\draw[<->, dashed, thick] (D) -- (C);
\draw[<->, dashed, thick] (D) -- (X);
\draw[<->, dashed, thick] (D) -- (Y);
\end{scope} \begin{scope}[xshift=3cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (B) {$B$};
\node[rv, above of=Y, yshift=-0.3cm] (C) {$C$};
\draw[<->, thick, color=blue] (B) -- (X);
\draw[<->, dashed, thick] (C) -- (X);
\draw[<->, thick, color=blue] (C) -- (Y);
\draw[<->, thick, color=blue] (B) -- (C);
\end{scope}
\end{tikzpicture} \qquad \boxed{\begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}[xshift=3cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (B) {$B$};
\node[rv, above of=Y, yshift=-0.3cm] (D) {$D$};
\draw[<->, dashed, thick, color=red] (B) -- (X);
\draw[<->, dashed, thick] (B) -- (Y);
\draw[<->, dashed, thick] (D) -- (X);
\draw[<->, dashed, thick] (D) -- (Y);
\draw[<->, dashed, thick] (B) -- (D);
\end{scope} \end{tikzpicture}}^{\,\color{red} 2} \qquad \begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\draw[<->, thick, color=blue] (X) -- (Y);
\end{scope} \end{tikzpicture}
\;\biggr], \quad \mathcal{R}=\{\{B,C,D \}\}.\]

* Because $B \noconfarc X \mid D$, we have

\[\mathcal{Q} = \biggl[\; \begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (B) {$B$};
\node[rv, above of=Y, yshift=-0.3cm] (C) {$C$};
\node[rv, above of=B, xshift=0.8cm, yshift=-0.3cm] (D) {$D$};
\draw[<->, thick, color=blue] (B) -- (X);
\draw[<->, dashed, thick] (C) -- (X);
\draw[<->, thick, color=blue] (C) -- (Y);
\draw[<->, dashed, thick] (D) -- (B);
\draw[<->, dashed, thick] (D) -- (C);
\draw[<->, dashed, thick] (D) -- (X);
\draw[<->, dashed, thick] (D) -- (Y);
\end{scope} \begin{scope}[xshift=3cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (B) {$B$};
\node[rv, above of=Y, yshift=-0.3cm] (C) {$C$};
\draw[<->, thick, color=blue] (B) -- (X);
\draw[<->, dashed, thick] (C) -- (X);
\draw[<->, thick, color=blue] (C) -- (Y);
\draw[<->, thick, color=blue] (B) -- (C);
\end{scope}
\end{tikzpicture} \qquad \boxed{\begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}[xshift=3cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (B) {$B$};
\node[rv, above of=Y, yshift=-0.3cm] (D) {$D$};
\draw[<->, dashed, thick] (B) -- (Y);
\draw[<->, dashed, thick, color=red] (D) -- (X);
\draw[<->, dashed, thick] (D) -- (Y);
\draw[<->, dashed, thick] (B) -- (D);
\end{scope} \end{tikzpicture}}^{\,\color{red} 1} \qquad \begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\draw[<->, thick, color=blue] (X) -- (Y);
\end{scope} \end{tikzpicture}
\;\biggr], \quad \mathcal{R}=\{\{B,C,D \}\}.\]

* Further, since $X \noconfarc D \mid B$, we get

\[\mathcal{Q} = \biggl[\; \begin{tikzpicture}
\tikzset{rv/.style={circle,inner sep=1pt,draw,font=\sffamily},
node distance=12mm, >=stealth}
\begin{scope}
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (B) {$B$};
\node[rv, above of=Y, yshift=-0.3cm] (C) {$C$};
\node[rv, above of=B, xshift=0.8cm, yshift=-0.3cm] (D) {$D$};
\draw[<->, thick, color=blue] (B) -- (X);
\draw[<->, dashed, thick] (C) -- (X);
\draw[<->, thick, color=blue] (C) -- (Y);
\draw[<->, dashed, thick] (D) -- (B);
\draw[<->, dashed, thick] (D) -- (C);
\draw[<->, dashed, thick] (D) -- (X);
\draw[<->, dashed, thick] (D) -- (Y);
\end{scope} \begin{scope}[xshift=3cm]
\node[rv] (X) {$X$};
\node[rv, right of=X, xshift=0.5cm] (Y) {$Y$};
\node[rv, above of=X, yshift=-0.3cm] (B) {$B$};
\node[rv, above of=Y, yshift=-0.3cm] (C) {$C$};