$M_{14}\left(\underset{\mathbf{C}_{i}\in\mathbf{C}_{M_{2}}(v)}{\bigsqcup}M_{2}(\mathbf{C}_{i})\sqcup\mathbf{E}\right)=M_{14}(\mathbf{E})\sqcup\left(\underset{\mathbf{C}_{i}\in\mathbf{C}_{M_{2}}(v)}{\bigsqcup}M_{2}(\mathbf{C}_{i})\right).$

Thus, we can write:

$M_{124}(\mathbf{E})=M_{14}(\mathbf{E})\sqcup\left(\underset{\mathbf{C}_{i}\in\mathbf{C}_{M_{2}}(v)}{\bigsqcup}M_{2}(\mathbf{C}_{i})\right).$

Finally, plugging $M_{14}(\mathbf{E})$ from Property 2 of Lemma 12 into the
above equation, we have:

$\displaystyle
M_{124}(\mathbf{E})=\left(\underset{e\in\overrightarrow{\mathbf{E}}}{\bigsqcup}M_{14}\left(\\{e\\}\sqcup\overline{\mathbf{E}}\right)\right)\sqcup\left(\underset{\mathbf{C}_{i}\in\mathbf{C}_{M_{2}}(v)}{\bigsqcup}M_{2}(\mathbf{C}_{i})\right).$

Therefore, the proof is complete.

### M. Proof of Proposition 18

Consider a PCCG $G=(\mathbf{V},\mathbf{E})$ with set of nodes $\mathbf{V}$ and
set of edges $\mathbf{E}$. Suppose that $v_{s}\rightarrow v_{d}$ is the only
oriented edge in the set $\mathbf{E}$, i.e.,
$\overrightarrow{\mathbf{E}}=\\{v_{s}\rightarrow v_{d}\\}$. By defining
$\mathbf{T}\triangleq Neigh(v_{d})$, we have:

$\displaystyle M_{14}\left(\\{v_{s}\rightarrow
v_{d}\\}\sqcup\overline{\mathbf{E}}\right)=M_{14}\left(\\{v_{s}\rightarrow
v_{d}\\}\sqcup\mathbf{E}^{\prime}\sqcup\overline{\mathbf{E}}\right)=\mathbf{E}_{M_{14}},$

where $\mathbf{E}^{\prime}=M_{14}(\\{v_{s}\rightarrow
v_{d}\\}\sqcup\overline{\mathbf{E}}[\mathbf{T}])\backslash\\{v_{s}\rightarrow
v_{d}\\}$. From Property 2 of Lemma 12, we can write:

$\displaystyle M_{14}\left(\\{v_{s}\rightarrow
v_{d}\\}\sqcup\mathbf{E}^{\prime}\sqcup\overline{\mathbf{E}}\right)=M_{14}\left(\mathbf{E}^{\prime}\sqcup\overline{\mathbf{E}}\right)\sqcup
M_{14}\left(\\{v_{s}\rightarrow v_{d}\\}\sqcup\overline{\mathbf{E}}\right).$

Furthermore, we have:

$\displaystyle M_{14}\left(\\{v_{s}\rightarrow
v_{d}\\}\sqcup\overline{\mathbf{E}}\right)\backslash\\{v_{s}\rightarrow
v_{d}\\}$ $\displaystyle=\mathbf{E}_{M_{14}}\backslash\\{v_{s}\rightarrow
v_{d}\\}$ $\displaystyle
M_{14}\left(\mathbf{E}^{\prime}\sqcup\overline{\mathbf{E}}\right)$
$\displaystyle=\mathbf{E}_{M_{14}}\backslash\\{v_{s}\rightarrow v_{d}\\}.$

Thus, we have:

$\displaystyle M_{14}\left(\\{v_{s}\rightarrow
v_{d}\\}\sqcup\overline{\mathbf{E}}\right)=M_{14}\left(\mathbf{E}^{\prime}\sqcup\overline{\mathbf{E}}\right)\sqcup\\{v_{s}\rightarrow
v_{d}\\}.$

Finally, we obtain from Property 2 in Lemma 12:

$\displaystyle DP[v_{s}\rightarrow v_{d}]=\left(\underset{v_{l}\rightarrow
v_{k}\in\overrightarrow{\mathbf{E}^{\prime}}}{\bigsqcup}DP[v_{l}\rightarrow
v_{k}]\right)\bigsqcup\left\\{v_{s}\rightarrow v_{d}\right\\}.$

### N. Proof of Theorem 19

We know that calling function in Algorithm 1, may cause multiple another calls
of this function in a recursive manner. Here, we prove that calling this
function with directed edge $v_{s}\rightarrow v_{d}$ as input cannot occurred
inside in calling another function with the same input as $v_{s}\rightarrow
v_{d}$. We prove this by using the following lemma:

###### Lemma 31

Given a PCCG $G=(\mathbf{V},\mathbf{E})$ with set of nodes $\mathbf{V}$ and
set of edges $\mathbf{E}$. For any $v_{s}\in\mathbf{V}$ and for any edge
$v_{r}\rightarrow v_{k}\in
M_{14}(\overline{\mathbf{E}}\sqcup\\{v_{s}\rightarrow v_{d}\\})$, there exists
a directed path from $v_{s}$ to $v_{r}$.

Proof  We prove this statement by an induction on the number of steps taken by
Meek function $M_{14}$. In the base case, if we apply Meek rule 1, then we
orient some edge $v_{d}\rightarrow v_{j}$. Thus, there is the directed path
$v_{s}\rightarrow v_{d}\rightarrow v_{j}$ from $v_{s}$ to $v_{j}$. Moreover,
if we apply Meek rule 4 in the first step, two edges like $v_{d}\rightarrow
v_{j}$ and $v_{k}\rightarrow v_{j}$ will be oriented (see Table 1) and there
is the directed path $v_{s}\rightarrow v_{d}\rightarrow v_{j}$ from $v_{s}$ to
$v_{j}$. Now, for the induction step, assume that induction hypothesis holds
up to step r, i.e., for any oriented edge like $v_{i}\rightarrow v_{r}$ from
Meek function $M_{1}$, there is a directed path from $v_{s}$ to $v_{r}$.
Suppose that in step r+1, a new edge like $v_{r}\rightarrow v_{k}$ is oriented
by applying Meek rule 1 on some edge $v_{i}\rightarrow v_{r}$. Since we know
that there is a directed path from $v_{s}$ to $v_{r}$, the same holds from
$v_{s}$ to $v_{k}$. In the case that new edge is oriented by applying Meek
function $M_{4}$ on some previous oriented edge like $v_{i}\rightarrow v_{r}$,
it can be easily seen that (see Table 1), there would be a directed edge from
$v_{r}$ to the head vertex of the newly oriented edge. Based on the induction
hypothesis we can infer that there is a directed path from $v_{s}$ to head
vertex of the new oriented edge and the proof is complete.
Based on Lemma 31, we will get a directed cycle if such a mentioned recursive
call is happened. In this scenario, we will have a directed path from node
$v_{s}$ to itself. As the underlying graph is a causal DAG, that cannot be
happened. Thus, we have not multiple function calls with the same input.
Additionally, as we have stored the resulted oriented edges after applying
Meek rules on that edge, we did not call that edge again. Therefore, we call
this function for each edge once. For filling all entries of DP table, we must
call this function $2|\mathbf{E}|$ times. Moreover, we have a nested for-loop
in each call which takes $\mathcal{O}(\Delta^{2})$ operations. Hence, in
total, the computational complexity would be in the order of
$\mathcal{O}(|\mathbf{E}|\Delta^{2})$.

### O. Proof of Lemma 20

We know $\mathbf{S}=\\{v_{i}\rightarrow
v|v_{i}\in\mathbf{I}\\}\sqcup\\{v\rightarrow
v_{o}|v_{o}\in\mathbf{O}\\}\subseteq\mathbf{E}$. From Property 2 of Lemma 12,
we have:

$\displaystyle
M_{14}(\mathbf{E})=\left(\underset{v_{i}\in\mathbf{I}}{\bigsqcup}M_{14}\left(\left\\{v_{i}\rightarrow
v\right\\}\sqcup\overline{\mathbf{E}}\right)\right)\bigsqcup\left(\underset{v_{o}\in\mathbf{O}}{\bigsqcup}M_{14}\left(\left\\{v\rightarrow
v_{o}\right\\}\sqcup\overline{\mathbf{E}}\right)\right).$

We define set of nodes $\mathbf{O}_{c}$ as
$\\{v_{o}|v_{o}\in\mathbf{O},\mathbf{I}\subseteq neigh(v_{o})\\}$. Hence, we
rewrite the above equation as the following:

$\displaystyle
M_{14}(\mathbf{E})=\left(\underset{v_{i}\in\mathbf{I}}{\bigsqcup}M_{14}\left(\left\\{v_{i}\rightarrow
v\right\\}\sqcup\overline{\mathbf{E}}\right)\right)$
$\displaystyle\bigsqcup\left(\underset{v_{o}\in\mathbf{O}_{c}}{\bigsqcup}M_{14}\left(\left\\{v\rightarrow
v_{o}\right\\}\sqcup\overline{\mathbf{E}}\right)\right)$
$\displaystyle\bigsqcup\left(\underset{v_{o}\in\mathbf{O}\backslash\mathbf{O}_{c}}{\bigsqcup}M_{14}\left(\left\\{v\rightarrow
v_{o}\right\\}\sqcup\overline{\mathbf{E}}\right)\right).$

For each node $v_{o}\in\mathbf{O}\backslash\mathbf{O}_{c}$, there exists a
node $v_{k}\in\mathbf{I}$ such that $v_{k}\notin neigh(v_{o})$, thus we have
$v\rightarrow v_{o}\in M_{14}(\\{v_{k}\rightarrow
v\\}\sqcup\overline{\mathbf{E}})$. Therefore, we have the following relation:

$\displaystyle M_{14}\left(\left\\{v\rightarrow
v_{o}\right\\}\sqcup\overline{\mathbf{E}}\right)\subseteq
M_{14}\left(\left\\{v_{k}\rightarrow
v\right\\}\sqcup\overline{\mathbf{E}}\right)\subseteq\underset{v_{i}\in\mathbf{I}}{\bigsqcup}M_{14}\left(\left\\{v_{i}\rightarrow
v\right\\}\sqcup\overline{\mathbf{E}}\right).$

Thus, we have:

$\displaystyle\underset{v_{o}\in\mathbf{O}\backslash\mathbf{O}_{c}}{\bigsqcup}M_{14}\left(\left\\{v\rightarrow
v_{o}\right\\}\sqcup\overline{\mathbf{E}}\right)\subseteq\underset{v_{i}\in\mathbf{I}}{\bigsqcup}M_{14}\left(\left\\{v_{i}\rightarrow
v\right\\}\sqcup\overline{\mathbf{E}}\right).$

Hence, we can write:

$\displaystyle M_{14}(\mathbf{E})$
$\displaystyle=\left(\underset{v_{i}\in\mathbf{I}}{\bigsqcup}M_{14}\left(\left\\{v_{i}\rightarrow
v\right\\}\sqcup\overline{\mathbf{E}}\right)\right)\bigsqcup\left(\underset{v_{o}\in\mathbf{O}_{c}}{\bigsqcup}M_{14}\left(\left\\{v\rightarrow
v_{o}\right\\}\sqcup\overline{\mathbf{E}}\right)\right)$
$\displaystyle=\underset{v_{l}\rightarrow
v_{k}\in\mathbf{S^{\prime}}}{\bigsqcup}M_{14}\left(\left\\{v_{l}\rightarrow
v_{k}\right\\}\sqcup\overline{\mathbf{E}}\right)$
$\displaystyle=\underset{v_{l}\rightarrow
v_{k}\in\mathbf{S^{\prime}}}{\bigsqcup}DP[v_{l}\rightarrow v_{k}],$

where $\mathbf{S^{\prime}}=\\{v_{i}\rightarrow
v|v_{i}\in\mathbf{I}\\}\sqcup\\{v\rightarrow
v_{o}|v_{o}\in\mathbf{O},\mathbf{I}\subseteq neigh(v_{o})\\}$.

### P. Proof of Theorem 21

Having $\mathbf{S}=\\{v_{i}\rightarrow
v|v_{i}\in\mathbf{I}\\}\sqcup\\{v\rightarrow v_{o}|v_{o}\in\mathbf{O}\\}$ and
$\overrightarrow{\mathbf{S}}=\overrightarrow{\mathbf{E}}$, from Theorem 17, we
have:

$\displaystyle
M_{124}(\mathbf{E})=\left(\underset{e\in\overrightarrow{\mathbf{E}}}{\bigsqcup}M_{14}(\\{e\\}\sqcup\overline{\mathbf{E}})\right)\sqcup\left(\underset{\mathbf{C}_{i}\in\mathbf{C}_{M_{2}}(v)}{\bigsqcup}M_{2}(\mathbf{C}_{i})\right).$

Substituting the first term with its equivalent term in Lemma 20, we have:

$\displaystyle M_{124}(\mathbf{E})=\left(\underset{v_{l}\rightarrow
v_{k}\in\mathbf{S^{\prime}}}{\bigsqcup}DP[v_{l}\rightarrow
v_{k}]\right)\bigsqcup\left(\underset{\mathbf{C}_{i}\in\mathbf{C}_{M_{2}}(v)}{\bigsqcup}M_{2}(\mathbf{C}_{i})\right),$

where $\mathbf{S^{\prime}}=\\{v_{i}\rightarrow
v|v_{i}\in\mathbf{I}\\}\sqcup\\{v\rightarrow v_{o}|v_{o}\in\mathbf{O}_{c}\\}$
and $\mathbf{O}_{c}=\\{v_{o}|v_{o}\in\mathbf{O},\mathbf{I}\subseteq
neigh(v_{o})\\}$. By defining
$\mathbf{I}_{neigh(v_{o})}=\\{v_{i}|v_{i}\in\mathbf{I}\cap neigh(v_{o})\\}$,
we have the following equation:

$\displaystyle\underset{\mathbf{C}_{i}\in\mathbf{C}_{M_{2}}(v)}{\bigsqcup}M_{2}(\mathbf{C}_{i})=\left\\{v_{i}\rightarrow
v_{o}|v_{i}\in\mathbf{I}_{neigh(v_{o})},v_{o}\in\mathbf{O}_{c}\right\\}\bigsqcup\left\\{v_{i}\rightarrow
v_{o}|v_{i}\in\mathbf{I}_{neigh(v_{o})},v_{o}\in\mathbf{O}\backslash\mathbf{O}_{c}\right\\}.$

From the definition of $\mathbf{O}_{c}$, we know that for each
$v_{o}\in\mathbf{O}_{c}$, we have $\mathbf{I}\subseteq neigh(v_{o})$. Hence,
for each $v_{o}\in\mathbf{O}_{c}$, we have
$\mathbf{I}_{neigh(v_{o})}=\mathbf{I}$. Thus, for the first term in the above
equation, we have:

$\left\\{v_{i}\rightarrow
v_{o}|v_{i}\in\mathbf{I}_{neigh(v_{o})},v_{o}\in\mathbf{O}_{c}\right\\}=\left\\{v_{i}\rightarrow
v_{o}|v_{i}\in\mathbf{I},v_{o}\in\mathbf{O}_{c}\right\\}.$

Therefore, it suffices to show that:

$\left\\{v_{i}\rightarrow
v_{o}|v_{i}\in\mathbf{I}_{neigh(v_{o})},v_{o}\in\mathbf{O}\backslash\mathbf{O}_{c}\right\\}\subseteq\underset{v_{l}\rightarrow
v_{k}\in\mathbf{S^{\prime}}}{\bigsqcup}DP[v_{l}\rightarrow v_{k}]$

Having $v_{i}\in\mathbf{I}_{neigh(v_{o})}$ and
$v_{o}\in\mathbf{O}\backslash\mathbf{O}_{c}$, for each edge
$v_{i}\;\rule[1.72218pt]{8.99994pt}{0.5pt}\;v_{o}\in\overline{\mathbf{E}}$,
there exists a node $v_{t}\in\mathbf{I}\backslash\mathbf{I}_{neigh(v_{o})}$,
and a sub-graph $\mathbf{E}[\\{v_{i},v_{o},v_{t},v\\}]=\\{v_{t}\rightarrow
v,v\rightarrow v_{o},v_{i}\rightarrow
v,v_{t}\;\rule[1.72218pt]{8.99994pt}{0.5pt}\;v_{i},v_{i}\;\rule[1.72218pt]{8.99994pt}{0.5pt}\;v_{o}\\}$
in the graph. Thus, we will have:

$v_{i}\rightarrow v_{o}\in DP[v_{t}\rightarrow v].$

Furthermore, we have $\\{v_{t}\rightarrow v\\}\subset\mathbf{S^{\prime}}$.
Thus, we can write:

$\\{v_{i}\rightarrow v_{o}\\}\subseteq DP[v_{t}\rightarrow
v]\subseteq\underset{v_{l}\rightarrow
v_{k}\in\mathbf{S^{\prime}}}{\bigsqcup}DP[v_{l}\rightarrow v_{k}].$

Hence, we can conclude that:

$\displaystyle M_{124}(\mathbf{E})=\left\\{\underset{v_{l}\rightarrow
v_{k}\in\mathbf{S^{\prime}}}{\bigsqcup}DP[v_{l}\rightarrow
v_{k}]\right\\}\bigsqcup\left(v_{i}\rightarrow v_{o}|v_{i}\in
I,v_{o}\in\mathbf{O}_{c}\right)$

where $\mathbf{S^{\prime}}=\\{v_{i}\rightarrow
v|v_{i}\in\mathbf{I}\\}\sqcup\\{v\rightarrow
v_{o}|v_{o}\in\mathbf{O},\mathbf{I}\subseteq neigh(v_{o})\\}$.

### Q. Proof of Lemma 22

We denote the obtained ICCGs with $G=(\mathbf{V},\mathbf{E})$. We know that
$\overrightarrow{\mathbf{E}}=\mathbf{S}=\\{v_{i}\rightarrow
v|v_{i}\in\mathbf{I}\\}\sqcup\\{v\rightarrow v_{o}|v_{o}\in\mathbf{O}\\}$ in
which $\mathbf{I}\subseteq\mathbf{C}_{k}$. We divide the problem of
calculating the lower bound into two cases. In the first case, all the edges
are from nodes in maximal clique toward the intervened node, $v$, i.e.,
$\mathbf{I}=\mathbf{C}_{k}$. In the second case, we consider that there is an
edge from a node in maximal clique toward node $v$ and also, there is an edge
from intervened node $v$ toward a node in maximal clique, i.e.,
$\mathbf{I}\subset\mathbf{C}_{k}$.
We use Theorem 21 for calculating number of oriented edges in the first case.
We have $\mathbf{I}=\mathbf{C}_{k}$. Thus, we know $\mathbf{O}_{c}=\emptyset$
and $\mathbf{S}=\\{v_{i}\rightarrow v|v_{i}\in\mathbf{C}_{k}\\}$. Hence, in
this case, number of oriented edges after applying Meek function $M_{124}$,
$|M_{124}(\mathbf{E})|$, is equal to the following:

$\displaystyle|M_{124}(\mathbf{E})|=L_{I}=\left|\underset{v_{i}\in\mathbf{I}}{\bigsqcup}DP[v_{i}\rightarrow
v]\right|.$

Now, we will investigate the second case. For sake of simplicity, first, we
assume that the set of nodes that have edges from nodes in maximal clique
$\mathbf{C}_{k}$ to intervened node $v$ is known. Then, we calculate the
minimum number of oriented edges for any possible orientation of edges between
maximal clique $\mathbf{C}_{k}$ and intervened node $v$. After intervention,
we have:

$\displaystyle M_{124}(\mathbf{E})=$ $\displaystyle
M_{124}\left(\left(\underset{v_{i}\in\mathbf{I}}{\bigsqcup}\\{v_{i}\rightarrow
v\\}\right)\bigsqcup\left(\underset{v_{o}\in
neigh(v)\backslash\mathbf{I}}{\bigsqcup}\\{v\rightarrow
v_{o}\\}\sqcup\overline{\mathbf{E}}\right)\right)$

Using Theorem 17, we decompose Meek function $M_{124}$ to Meek functions
$M_{2}$ and $M_{14}$:

$\displaystyle M_{124}(\mathbf{E})=$ $\displaystyle
M_{14}\left(\left(\underset{v_{i}\in\mathbf{I}}{\bigsqcup}\\{v_{i}\rightarrow
v\\}\right)\bigsqcup\left(\underset{v_{o}\in
neigh(v)\backslash\mathbf{I}}{\bigsqcup}\\{v\rightarrow
v_{o}\\}\sqcup\overline{\mathbf{E}}\right)\right)\bigsqcup$ $\displaystyle
M_{2}\left(\left(\underset{v_{i}\in\mathbf{I}}{\bigsqcup}\\{v_{i}\rightarrow
v\\}\right)\bigsqcup\left(\underset{v_{o}\in
neigh(v)\backslash\mathbf{I}}{\bigsqcup}\\{v\rightarrow
v_{o}\\}\sqcup\overline{\mathbf{E}}\right)\right).$

Based on Property 2 in Lemma 12, we extract mixed edge union from inside of
Meek function $M_{14}$:

$\displaystyle M_{124}(\mathbf{E})=$
$\displaystyle\left(\underset{v_{i}\in\mathbf{I}}{\bigsqcup}M_{14}(\\{v_{i}\rightarrow
v\\}\sqcup\overline{\mathbf{E}})\right)\bigsqcup\left(\underset{v_{o}\in
neigh(v)\backslash\mathbf{I}}{\bigsqcup}M_{14}(\\{v\rightarrow
v_{o}\\}\sqcup\overline{\mathbf{E}})\right)\bigsqcup$ $\displaystyle M_{2}$
$\displaystyle\left(\left(\underset{v_{i}\in\mathbf{I}}{\bigsqcup}\\{v_{i}\rightarrow
v\\}\right)\bigsqcup\left(\underset{v_{o}\in
neigh(v)\backslash\mathbf{I}}{\bigsqcup}\\{v\rightarrow
v_{o}\\}\sqcup\overline{\mathbf{E}}\right)\right).$

We know that $\mathbf{I}\subseteq\mathbf{C}_{k}$, therefore we have:

$\displaystyle
neigh(v)\backslash\mathbf{I}=neigh(v)\backslash\mathbf{C}_{k}\cup\mathbf{C}_{k}\backslash\mathbf{I}.$

Thus, we can write:

$\displaystyle\underset{v_{o}\in
neigh(v)\backslash\mathbf{I}}{\bigsqcup}M_{14}(\\{v\rightarrow
v_{o}\\}\sqcup\overline{\mathbf{E}})=\left(\underset{v_{o}\in
neigh(v)\backslash\mathbf{C}_{k}}{\bigsqcup}M_{14}(\\{v\rightarrow
v_{o}\\}\sqcup\overline{\mathbf{E}})\right)\bigsqcup\left(\underset{v_{o}\in\mathbf{C}_{k}\backslash\mathbf{I}}{\bigsqcup}M_{14}(\\{v\rightarrow
v_{o}\\}\sqcup\overline{\mathbf{E}})\right).$

Substituting $M_{14}$ function with the DP value in Proposition 18, we will
have:

$\displaystyle\underset{v_{o}\in
neigh(v)\backslash\mathbf{I}}{\bigsqcup}M_{14}(\\{v\rightarrow
v_{o}\\}\sqcup\overline{\mathbf{E}})=\left(\underset{v_{o}\in
neigh(v)\backslash\mathbf{C}_{k}}{\bigsqcup}DP[v\rightarrow
v_{o}]\right)\bigsqcup\left(\underset{v_{o}\in\mathbf{C}_{k}\backslash\mathbf{I}}{\bigsqcup}DP[v\rightarrow
v_{o}]\right).$

In the other hand, we have:

$\displaystyle\underset{v_{i}\in\mathbf{I}}{\bigsqcup}M_{14}(\\{v_{i}\rightarrow
v\\}\sqcup\overline{\mathbf{E}})=\underset{v_{i}\in\mathbf{I}}{\bigsqcup}DP[v_{i}\rightarrow
v].$

Therefore, we can write:

$\displaystyle M_{124}(\mathbf{E})=$ $\displaystyle\left(\underset{v_{o}\in
neigh(v)\backslash\mathbf{C}_{k}}{\bigsqcup}DP[v\rightarrow
v_{o}]\right)\bigsqcup\left(\underset{v_{o}\in\mathbf{C}_{k}\backslash\mathbf{I}}{\bigsqcup}DP\left[\\{v\rightarrow
v_{o}\\}\right]\right)\bigsqcup$
$\displaystyle\left(\underset{v_{i}\in\mathbf{I}}{\bigsqcup}DP[v_{i}\rightarrow
v]\right)\bigsqcup
M_{2}\left(\left(\underset{v_{i}\in\mathbf{I}}{\bigsqcup}\\{v_{i}\rightarrow
v\\}\right)\bigsqcup\left(\underset{v_{o}\in
neigh(v)\backslash\mathbf{I}}{\bigsqcup}\\{v\rightarrow
v_{o}\\}\sqcup\overline{\mathbf{E}}\right)\right).$

According to Lemma 16, we can write:

$\displaystyle
M_{2}\left(\left(\underset{v_{i}\in\mathbf{I}}{\bigsqcup}\\{v_{i}\rightarrow
v\\}\right)\bigsqcup\left(\underset{v_{o}\in
neigh(v)\backslash\mathbf{I}}{\bigsqcup}\\{v\rightarrow
v_{o}\\}\sqcup\overline{\mathbf{E}}\right)\right)=$
$\displaystyle\left\\{v_{i}\rightarrow v_{o}|v_{i}\in
I,v_{o}\in\mathbf{C}_{k}\backslash\mathbf{I}\right\\}\sqcup\left\\{v_{i}\rightarrow
v_{o}|v_{i}\in I,v_{o}\in neigh(v)\cap
neigh(v_{i})\backslash\mathbf{C}_{k}\right\\}.$

Therefore, we can obtain the result of applying Meek function $M_{124}$ on set
$\mathbf{E}$ with the following equation:

$\displaystyle
M_{124}(\mathbf{E})=\mathbf{T}_{1}\sqcup\mathbf{T}_{2}\sqcup\mathbf{T}_{3}\sqcup\mathbf{T}_{4}.$

where,

$\displaystyle\mathbf{T}_{1}=\underset{v_{o}\in
neigh(v)\backslash\mathbf{C}_{k}}{\bigsqcup}DP[v\rightarrow v_{o}],$
$\displaystyle\mathbf{T}_{2}=\left\\{v_{i}\rightarrow
v_{o}|v_{i}\in\mathbf{I},v_{o}\in\mathbf{C}_{k}\backslash\mathbf{I}\right\\},$
$\displaystyle\mathbf{T}_{3}=\left(\underset{v_{i}\in\mathbf{I}}{\bigsqcup}DP[v_{i}\rightarrow
v]\bigsqcup\left\\{v_{i}\rightarrow v_{o}|v_{i}\in I,v_{o}\in neigh(v)\cap
neigh(v_{i})\backslash\mathbf{C}_{k}\right\\}\right)\backslash\mathbf{T}_{1},$
$\displaystyle\mathbf{T}_{4}=\left(\underset{v_{o}\in\mathbf{C}_{k}\backslash\mathbf{I}}{\bigsqcup}DP[v\rightarrow
v_{o}]\right)\backslash\mathbf{T}_{1}.$

Now, our goal is to calculate $|M_{124}(\mathbf{E})|$. To do so, we want to
prove that the intersection of any two sets selected from the sets
$\mathbf{T}_{1},\mathbf{T}_{2},\mathbf{T}_{3},\mathbf{T}_{4}$ is empty. In
order to show this, we first state the following Lemma 32.

###### Lemma 32

Consider a UCCG $G=(\mathbf{V},\mathbf{E})$ with set of nodes $\mathbf{V}$ and
set of edges $\mathbf{E}$. Suppose that there exists a maximal clique
$\mathbf{C}_{k}$ in the neighborhood of node $v$. The following relations
hold:

  * •

For any
$v_{1}\;\rule[1.72218pt]{8.99994pt}{0.5pt}\;v_{2}\in\overline{\mathbf{E}}[\mathbf{C}_{k}]$
and $v_{i}\in\mathbf{C}_{k}$, we have $v_{1}\rightarrow v_{2}\notin
DP[v_{i}\rightarrow v]$.

  * •

For any
$v_{1}\;\rule[1.72218pt]{8.99994pt}{0.5pt}\;v_{2}\in\overline{\mathbf{E}}[Neigh(v)]$
and $v_{o}\in neigh(v)$, we have $v_{1}\rightarrow v_{2}\notin DP[v\rightarrow
v_{o}]\backslash\\{v\rightarrow v_{o}\\}$.

  * •

For any
$\\{v_{1}\;\rule[1.72218pt]{8.99994pt}{0.5pt}\;v_{2},v_{3}\;\rule[1.72218pt]{8.99994pt}{0.5pt}\;v_{4}\\}\subseteq\\{v\;\rule[1.72218pt]{8.99994pt}{0.5pt}\;v_{t}|v_{t}\in\mathbf{C}_{k}\\}$,
we have $v_{1}\rightarrow v_{2}\notin DP[v_{3}\rightarrow v_{4}]$.

Proof  It can be shown that there exist a DAG in the Markov equivalence class
of graph $G$, such that this DAG consists of some edges that are oriented from
nodes in a clique in the neighborhood of node $v$ to this node (see
Proposition 6 in Hauser and Buhlmann (2014)). We call such orientations in
which there exist a DAG in the MEC as valid orientations. Based on this fact,
we prove the relations by contradiction. For proving the first relation,
assume that we have $v_{1}\rightarrow v_{2}\in DP[v_{i}\rightarrow v]$. Thus,
according to Lemma 31, there exists a directed path from node $v$ to node
$v_{2}$. As $v_{2}$ and $v_{i}$ are in the maximal clique $\mathbf{C}_{k}$, we
can have valid orientations of $v_{2}\rightarrow v$ and $v_{i}\rightarrow v$
without making a new v-structure. Hence, there would be a directed cycle
$v\rightarrow\cdots\rightarrow v_{2}\rightarrow v$ which is a contradiction.
Therefore, there exists no DAG and we can imply that: $v_{1}\rightarrow
v_{2}\notin DP[v_{i}\rightarrow v]$.

In order to show the second relation, suppose that we have $v_{1}\rightarrow
v_{2}\in DP[v\rightarrow v_{o}]$. We partition the problem in three cases:
$v_{2}=v$, $v_{2}=v_{o}$ and $v_{2}\in neigh(v)\backslash v_{o}$. In the first
case, according to Lemma 31, there will be a directed path $v\rightarrow
v_{o}...\rightarrow v$ which is a directed cycle. In the second case,
according to Lemma 31, there will be a directed path
$v_{o}\rightarrow...\rightarrow v_{1}\rightarrow v_{o}$ which is a directed
cycle. In the third case, having the valid orientations $v_{2}\rightarrow v$
and $v\rightarrow v_{o}$, we have a directed path $v\rightarrow
v_{o}...\rightarrow v_{2}\rightarrow v$ which is a directed cycle and there
exists no DAG. This is a contradiction.

For proving the third relation, assume we have $v_{1}\rightarrow v_{2}\in
DP[v_{3}\rightarrow v_{4}]$. This means that orienting the edge
$v_{3}\rightarrow v_{4}$ orients the edge $v_{1}\rightarrow v_{2}$, and we
cannot have a DAG including directed edges $v_{3}\rightarrow v_{4}$ and
$v_{2}\rightarrow v_{1}$. However, according to Proposition 6 in Hauser and
Buhlmann (2014), such orientations are valid orientations and there exists a
DAG, including those directed edges. Thus, this is a contradiction and the
proof is complete.

According to Lemma 32, we will show that intersection of sets
$\mathbf{T}_{1},\mathbf{T}_{2},\mathbf{T}_{3},\mathbf{T}_{4}$ is empty. Hence,
the number of elements in $M_{124}(\mathbf{E})$, i.e.,
$|M_{124}(\mathbf{E})|$, can be computed by adding the number of elements in
each of the sets
$\mathbf{T}_{1},\mathbf{T}_{2},\mathbf{T}_{3},\mathbf{T}_{4}$.

First, it can be seen that
$\overline{\mathbf{T}}_{2}\subseteq\overline{\mathbf{E}}[\mathbf{C}_{k}]$.
Furthermore, based on the second relation in Lemma 32, we cannot find any edge
$v_{1}\rightarrow v_{2}\in\mathbf{T}_{1}$ for nodes
$v_{1},v_{2}\in\mathbf{C}_{k}$. Therefore, we have
$\overline{\mathbf{T}}_{1}\cap\overline{\mathbf{E}}[\mathbf{C}_{k}]=\emptyset$.
Additionally, we already removed all $\mathbf{T}_{1}$ elements from the sets
$\mathbf{T}_{3}$ and $\mathbf{T}_{4}$. Thus, we can write:

$\displaystyle\mathbf{T}_{1}\cap\left(\mathbf{T}_{2}\sqcup\mathbf{T}_{3}\sqcup\mathbf{T}_{4}\right)=\emptyset.$

In the following we prove that
$\overline{\mathbf{T}}_{3}\cap\overline{\mathbf{E}}[\mathbf{C}_{k}]=\emptyset$
and
$\overline{\mathbf{T}}_{4}\cap\overline{\mathbf{E}}[\mathbf{C}_{k}]=\emptyset$.
Based on the second relation in Lemma 32, we cannot find any edge
$v_{1}\rightarrow v_{2}\in\mathbf{T}_{4}$ for set of nodes
$v_{1},v_{2}\in\mathbf{C}_{k}$. Moreover, we can define the following two sets
$\mathbf{T}_{3}^{1}$ and $\mathbf{T}_{3}^{2}$ such that
$\mathbf{T}_{3}=\mathbf{T}_{3}^{1}\sqcup\mathbf{T}_{3}^{2}$:

$\displaystyle\mathbf{T}_{3}^{1}=\left(\underset{v_{i}\in\mathbf{I}}{\bigsqcup}DP[v_{i}\rightarrow
v]\right)\backslash\mathbf{T}_{1},$
$\displaystyle\mathbf{T}_{3}^{2}=\left(\bigsqcup\left\\{v_{i}\rightarrow
v_{o}|v_{i}\in I,v_{o}\in neigh(v)\cap
neigh(v_{i})\backslash\mathbf{C}_{k}\right\\}\right)\backslash\mathbf{T}_{1}.$

We know that
$\overline{\mathbf{T}}_{3}^{2}\cap\overline{\mathbf{E}}[\mathbf{C}_{k}]=\emptyset$.
It suffices to show
$\overline{\mathbf{T}}_{3}^{1}\cap\overline{\mathbf{E}}[\mathbf{C}_{k}]=\emptyset$.
Again based on the first relation in Lemma 32, we cannot find any edge
$v_{1}\rightarrow v_{2}\in\mathbf{T}_{3}^{1}$ for nodes
$v_{1},v_{2}\in\mathbf{C}_{k}$. Hence, we have
$\overline{\mathbf{T}}_{3}\cap\overline{\mathbf{E}}[\mathbf{C}_{k}]=\emptyset$
and we can write:

$\displaystyle\mathbf{T}_{2}\cap\left(\mathbf{T}_{3}\sqcup\mathbf{T}_{4}\right)=\emptyset.$

Finally, we will show that: $\mathbf{T}_{3}\cap\mathbf{T}_{4}=\emptyset.$ To
do so, we prove the following two relations:

$\displaystyle\overline{\mathbf{T}}_{3}\subseteq\overline{\mathbf{E}}[Neigh(v)]\backslash\\{v\;\rule[1.72218pt]{8.99994pt}{0.5pt}\;v_{o}|v_{o}\in\mathbf{C}_{k}\backslash\mathbf{I}\\},$
(16)
$\displaystyle\overline{\mathbf{T}}_{4}\subseteq\\{v\;\rule[1.72218pt]{8.99994pt}{0.5pt}\;v_{o}|v_{o}\in\mathbf{C}_{k}\backslash\mathbf{I}\\}\sqcup\overline{\mathbf{E}}\backslash\overline{\mathbf{E}}[Neigh(v)].$
(17)

For proving the relation (5), consider set $\mathbf{T}_{3}$. We know
$\overline{\mathbf{T}}_{3}^{2}\subseteq\overline{\mathbf{E}}[Neigh(v)]\backslash\\{v\;\rule[1.72218pt]{8.99994pt}{0.5pt}\;v_{o}|v_{o}\in\mathbf{C}_{k}\backslash\mathbf{I}\\}$.
Thus, it suffices to show:
$\overline{\mathbf{T}}_{3}^{1}\subseteq\overline{\mathbf{E}}[Neigh(v)]\backslash\\{v\;\rule[1.72218pt]{8.99994pt}{0.5pt}\;v_{o}|v_{o}\in\mathbf{C}_{k}\backslash\mathbf{I}\\}$.
Based on Proposition 18, in the first step of DP calculation for each edge
$v_{i}\rightarrow v$, we orient the edges inside the sub-graph
$\overline{\mathbf{E}}[Neigh(v)]$. The edges that are in $DP[v_{i}\rightarrow
v]$ and $\overline{\mathbf{E}}[Neigh(v)]$, can be categorized into two types.
In the first type, at least one of the endpoint of the edge is $v$. According
to third relation in Lemma 32, for these edges like $v\rightarrow v_{2}$, we
cannot orient edges $v\;\rule[1.72218pt]{8.99994pt}{0.5pt}\;v_{2}$ for any
$v_{2}\in\mathbf{C}_{k}$. Thus, we conclude that: $M_{14}(\\{v\rightarrow
v_{2}\\}\sqcup\overline{\mathbf{E}})\subseteq\mathbf{T}_{1}$. For the second
type of the edges, none of the endpoints of edges is the node $v$. For this
type of edges like $v_{1}\rightarrow v_{2}$, we cannot have
$\\{v_{1},v_{2}\\}\subseteq\mathbf{C}_{k}$ due to the first relation in Lemma
32. Furthermore, we cannot have $v_{2}\in\mathbf{C}_{k}$. Since if we have
$v_{2}\in\mathbf{C}_{k}$, then $v_{1}\not\in\mathbf{C}_{k}$. Moreover, based
on Proposition 6 in Hauser and Buhlmann (2014), by considering the valid
orientation $v_{2}\rightarrow v$, we will have a cycle as $\\{v\rightarrow
v_{1},v_{1}\rightarrow v_{2},v_{2}\rightarrow v\\}$. Additionally, for each
edge of this type there is always an edge $v\rightarrow v_{2}$, where
$v_{2}\in neigh(v)\backslash\mathbf{C}_{k}$. Therefore, it suffices to show
that, $\mathbf{E}_{1}\backslash\mathbf{E}_{1}[Neigh(v)]\subseteq
M_{14}(\\{v\rightarrow v_{2}\\}\sqcup\overline{\mathbf{E}})$, where
$\mathbf{E}_{1}=M_{14}(\\{v_{1}\rightarrow
v_{2}\\}\sqcup\overline{\mathbf{E}})$. We depict all possible skeletons in
Table 6. Note that we consider the cases in which applying Meek function
orients edges outside the sub-graph $\overline{\mathbf{E}}[Neigh(v)]$.
Therefore, in all of these cases $v_{3}\notin neigh(v)$. Additionally, in all
of these cases, the red edges are the ones that have been oriented as a result
of applying Meek function $M_{14}$ on $v_{1}\rightarrow v_{2}$, and as can be
seen, these edges are also oriented as a result of applying Meek functions
$M_{14}$ on $v\rightarrow v_{2}$. Based on the Proposition 18, for discovering
more edges’ orientation outside the sub-graph
$\overline{\mathbf{E}}[Neigh(v)]$, we must compute DP function in the sub-
graph $\overline{\mathbf{E}}[Neigh(v_{3})]$ ,where only red edges are
oriented. Thus, as we depict all possible cases, we conclude that every edges
that will be oriented outside the sub-graph $\overline{\mathbf{E}}[Neigh(v)]$
as a result of $M_{14}(\\{v_{1}\rightarrow
v_{2}\\}\sqcup\overline{\mathbf{E}})$ is also in $M_{14}(\\{v\rightarrow
v_{2}\\}\sqcup\overline{\mathbf{E}})\subseteq\mathbf{T}_{1}$. Thus, we have
$\overline{\mathbf{T}}_{3}\subseteq\overline{\mathbf{E}}[Neigh(v)]$. In
addition, based on the third relation in Lemma 32, no edge that is between
node $v$ and clique $\mathbf{C}_{k}$ will be oriented in $\mathbf{T}_{3}^{1}$.
Thus, we can write:

$\displaystyle\overline{\mathbf{T}}_{3}\subseteq\overline{\mathbf{E}}[Neigh(v)]\backslash\\{v\;\rule[1.72218pt]{8.99994pt}{0.5pt}\;v_{o}|v_{o}\in\mathbf{C}_{k}\backslash\mathbf{I}\\}$

Table 6: Different orientations for applying Meek function on $v_{i}\rightarrow v$ Case 1 | Case 2 | Case 3
---|---|---
$v_{i}$$v_{1}$$v$$v_{4}$$v_{2}$$v_{3}$ | $v_{i}$$v_{1}$$v$$v_{4}$$v_{2}$$v_{3}$ | $v_{i}$$v_{1}$$v$$v_{2}$$v_{3}$

For relation (6), based on Lemma 32, the result of applying Meek function
$M_{14}$ on set $\\{v\rightarrow v_{o}\\}\cup\overline{\mathbf{E}}$ cannot
orient any edge inside the sub-graph
$\overline{\mathbf{E}}[Neigh(v)]\backslash\\{v\rightarrow v_{o}\\}$. According
to these two relations, we can write:

$\displaystyle\mathbf{T}_{3}\cap\mathbf{T}_{4}=\emptyset.$

To wrap up, the following equation holds:

$\displaystyle\mathbf{T}_{1}\cap\left(\mathbf{T}_{2}\sqcup\mathbf{T}_{3}\sqcup\mathbf{T}_{4}\right)=\emptyset,$
$\displaystyle\mathbf{T}_{2}\cap\left(\mathbf{T}_{3}\sqcup\mathbf{T}_{4}\right)=\emptyset,$
$\displaystyle\mathbf{T}_{3}\cap\mathbf{T}_{4}=\emptyset.$

Hence, we will have:

$\displaystyle|M_{124}(\mathbf{E})|=|\mathbf{T}_{1}|+|\mathbf{T}_{2}|+|\mathbf{T}_{3}|+|\mathbf{T}_{4}|.$

Now, we can exactly compute the number of oriented edges after applying Meek
function $M_{124}$ on set $\mathbf{E}$. We can compute $\mathbf{T}_{1}$ from
the DP table. $\mathbf{T}_{2}$ can also be obtained easily. Now, we want to
find the minimum value for the size of sets $\mathbf{T}_{3}$ and
$\mathbf{T}_{4}$. First, we consider the set $\mathbf{T}_{3}$. Recall that the
definitions of $P_{j}$ and $Q_{j}$ are:

$\displaystyle
P_{j}\triangleq\underset{|\mathbf{I}|=j,\mathbf{I}\subset\mathbf{C}_{k}\;\;\;}{min}\underset{v_{i}\in\mathbf{I}}{max\;}\left|\left(DP[v_{i}\rightarrow
v]\underset{v_{o}\in neigh(v_{i})\cap
neigh(v)\backslash\mathbf{C}_{k}}{\bigsqcup}\\{v_{i}\rightarrow
v_{o}\\}\right)\backslash\mathbf{T}_{1}\right|$ $\displaystyle
Q_{j}\triangleq\underset{|\mathbf{O}|=j,\mathbf{O}\subset\mathbf{C}_{k}\;\;\;}{min}\underset{v_{o}\in\mathbf{O}}{max\;}|DP[v\rightarrow
v_{o}]\backslash\mathbf{T}_{1}|.$

Now, it can be seen that:

$\displaystyle\underset{v_{i}\in\mathbf{I}}{max\;}$
$\displaystyle\left|\left(DP[v_{i}\rightarrow v]\underset{v_{o}\in
neigh(v_{i})\cap
neigh(v)\backslash\mathbf{C}_{k}}{\bigsqcup}\\{v_{i}\rightarrow
v_{o}\\}\right)\backslash\mathbf{T}_{1}\right|\leq$
$\displaystyle\left|\left(\underset{v_{i}\in\mathbf{I}}{\bigsqcup}DP[v_{i}\rightarrow
v]\bigsqcup\left\\{v_{i}\rightarrow v_{o}|v_{i}\in I,v_{o}\in neigh(v)\cap
neigh(v_{i})\backslash\mathbf{C}_{k}\right\\}\right)\backslash\mathbf{T}_{1}\right|.$

But the right hand side of the above inequality is $|\mathbf{T}_{3}|$. Hence,
we can imply that $P_{j}\leq|\mathbf{T}_{3}|$. Similarly, we can show that
$Q_{j}\leq|\mathbf{T}_{4}|$.

Finally, we will have:

$\displaystyle\left|\mathbf{T}_{1}\right|=|\mathbf{R}|,$
$\displaystyle\left|\mathbf{T}_{2}\right|=|\mathbf{I}|(|\mathbf{C}_{k}|-|\mathbf{I}|),$
$\displaystyle\left|\mathbf{T}_{3}\right|\geq P_{j},$
$\displaystyle\left|\mathbf{T}_{4}\right|\geq Q_{j}.$

Thus, when the set $\mathbf{I}$ is known, we will have:

$\displaystyle|M_{124}(\mathbf{E})|\geq|\mathbf{R}|+P_{|I|}+Q_{(|\mathbf{C}_{k}|-|I|)}+|I|(|\mathbf{C}_{k}|-|I|)+(|\mathbf{C}_{k}|-2).$

Note that for obtaining $P_{|I|}$ and $Q_{(|\mathbf{C}_{k}|-|I|)}$, we just
consider two edges between the $\mathbf{C}_{k}$ and $v$. Therefore, the last
term is for those remaining $|\mathbf{C}_{k}|-2$ edges that are between clique
and node $v$ and they will definitely be oriented after intervention. Note
that, based on the second and third relation, these edges have not been
considered in computing $Q_{j}$ and $P_{j}$ values and also they have not been
oriented in set $\mathbf{R}$. If we consider all possible sets for set
$\mathbf{I}$, where $|\mathbf{I}|=l$, we will have:

$\displaystyle|M_{124}(\mathbf{E})|\geq
L_{C}=|\mathbf{R}|+\underset{l=\\{1,...,|\mathbf{C}_{k}|-1\\}}{\min}P_{l}+Q_{|\mathbf{C}_{k}|-l}+|l|(|\mathbf{C}_{k}|-|l|)+(|\mathbf{C}_{k}|-2).$

Finally we can infer that:

$\displaystyle L(\mathbf{C}_{k},v)=\min(L_{I},L_{C}).$

### R. Proof of Theorem 24

After intervention on node $v$, we will discover orientations of edges in the
neighborhood of intervened node $v$. We denote the obtained ICCG by
$G^{\prime}=(\mathbf{V},\mathbf{E}^{\prime})$. Additionally, we denote set of
nodes that have edges toward node $v$ with $\mathbf{I}$. Furthermore, we
denote the set of all maximal cliques in the neighborhood of node $v$ by
$\mathbf{C}(v)$. As edges that are orientated from intervention do not
generate a new v-structure in the graph, there exists a maximal clique
$\mathbf{C}_{k}\in\mathbf{C}(v)$, such that
$\mathbf{I}\subseteq\mathbf{C}_{k}$.

After intervention, two cases can be considered: (a) All edges are outgoing
from node $v$ toward the nodes in the neighborhood of node $v$ (b) At least
there exists one edge from a node in the neighborhood of node $v$ to node $v$.
In the first case, i.e., $\mathbf{I}=\emptyset$, using Theorem 21, the number
of oriented edges after intervention is equal to the following equation:

$\displaystyle|M_{124}(\mathbf{E}^{\prime})|=\Bigg{|}\underset{v_{o}\in
neigh(v)}{\bigsqcup}DP[v\rightarrow v_{o}]\Bigg{|}.$

In the second case, i.e., $\mathbf{I}\subseteq\mathbf{C}_{k}$ and
$|\mathbf{I}|>0$, based on Lemma 22, the lower bound on number of oriented
edges can be written as follows:

$\displaystyle|M_{124}(\mathbf{E}^{\prime})|\geq\underset{\mathbf{C}_{k}\in\mathbf{C}(v)}{min}L(\mathbf{C}_{k},v).$

Hence, the lower bound on number of oriented edges after intervention on node
$v$, $L(v)$, can be calculated as the following:

$\displaystyle|M_{124}(\mathbf{E}^{\prime})|\geq
L(v)=min\Bigg{(}\Bigg{|}\underset{v_{o}\in neigh(v)}{\bigsqcup}DP[v\rightarrow
v_{o}]\Bigg{|},\underset{\mathbf{C}_{k}\in\mathbf{C}(v)}{min}L(\mathbf{C}_{k},v)\Bigg{)}.$

### S. Proof of Theorem 28

We know the PCCG $G$ consists of the combination of both directed and
undirected edges. For the “only if” part, we know that there is a causal DAG
with the same skeleton as graph $G$, including directed edges in $\mathbf{E}$.
We can imply that there is no cycle in $\mathbf{E}$ and all edges in
$\mathbf{E}$ are consistent. For the ”if” part, we know that there is no cycle
in $\mathbf{E}$ and the set $\mathbf{E}$ is consistent. We want to show that
there will be a causal DAG with the same skeleton as graph $G$, including
directed edges in $\mathbf{E}$.

To prove this, we will use an algorithm that constructs a DAG from our graph
$G$, if the mentioned constraints are satisfied. Algorithm 6 takes $G$ as its
input and returns a causal DAG, including no v-structure if the constraints
are satisfied. This algorithm guarantees that generated DAG contains all
directed edges in $\mathbf{E}$ and has the same skeleton as
$\overline{\mathbf{E}}$ and it has no v-structure. In Line 5 in Algorithm 6,
we apply Meek functions $M_{124}$ on set $\mathbf{E}$. Through Lines 6-9, we
orient undirected edges that are existed in set $\mathbf{E}$. In Line 7, we
select an arbitrary node, and in Line 8, we orient all undirected edges in the
neighborhood of this node as out-going edges. Thus, all the edges in the
neighborhood of this node will be oriented and we denote the set of these
oriented edges by $\mathbf{S}$. In Line 9, we obtain the result of applying
Meek functions $M_{124}$ on set $\mathbf{S}\sqcup\overline{\mathbf{E}}$. Also,
we add the oriented edges to the output DAG $\mathscr{G}$.

Algorithm 6 Causal DAG Construction Algorithm

1:Input: PCCG $G=(\mathbf{V},\mathbf{E})$

2:Output: DAG
$\mathscr{G}=(\mathbf{V}_{\mathscr{G}},\mathbf{E}_{\mathscr{G}})$

3:function $PDAG2DAG$($G$)

4: $\mathbf{V}_{\mathscr{G}}\leftarrow\mathbf{V}$

5: $\mathbf{E}_{\mathscr{G}}\leftarrow M_{124}(\mathbf{E})$

6: while $|\mathbf{E}|\neq|\overrightarrow{\mathbf{E}}_{\mathscr{G}}|$ do

7: $v\leftarrow$ an arbitrary node from $\\{v_{l}|\exists
v_{k}\in{\mathbf{V}}_{\mathscr{G}},v_{l}\;\rule[1.72218pt]{8.99994pt}{0.5pt}\;v_{k}\in{\mathbf{E}}_{\mathscr{G}}\\}$

8: $\mathbf{S}\leftarrow\\{v_{i}\rightarrow v|v_{i}\rightarrow
v\in\mathbf{E}_{\mathscr{G}}\\}\sqcup\\{v\rightarrow v_{o}|v\rightarrow
v_{o}\in\mathbf{E}_{\mathscr{G}}\text{ or
}v\;\rule[1.72218pt]{8.99994pt}{0.5pt}\;v_{o}\in\mathbf{E}_{\mathscr{G}}\\}$

9: $\mathbf{E}_{\mathscr{G}}\leftarrow
M_{124}({\mathbf{E}}_{\mathscr{G}}\sqcup\mathbf{S})$

10: return $\mathscr{G}$

Based on our assumptions, we know that PDAG $G$ has no cycle. Additionally,
the following lemma expresses it has no v-structure.

###### Lemma 33

For any graph $G=(\mathbf{V},\mathbf{E})$, there is no v-structure in
$\mathbf{E}$ if $\mathbf{E}$ is a consistent set.

Proof  We prove this by contradiction. Suppose a v-structure like
$\\{v_{i}\rightarrow v_{j},v_{j}\leftarrow v_{k}\\}$ exists in $\mathbf{E}$.
Thus, we have $v_{j}\rightarrow v_{k}\in DP[v_{i}\rightarrow v_{j}]$. This is
a contradiction because $\mathbf{E}$ is a consistent set.
It suffices to show no new cycle and no new v-structure will be generated
during running Algorithm 6. First, we will show that no v-structure will be
appeared in the output graph of Algorithm 6.

To do so, we will prove that orienting further edges, either by applying Meek
function $M_{124}$ on set $\mathbf{E}$ or adding new directed edges such as
those in the constructing set $\mathbf{S}$ in Algorithm 6, does not generate
any new v-structure. Before providing the proof, we state the following lemma
that helps in proving mentioned statement.

| $v_{s}$$v_{d}$$v_{j}$
---
| $v_{s}$$v_{d}$$v_{j}$
---
| $v_{s}$$v_{d}$$v_{i}$$v_{j}$
---
(a) | (b) | (c)
| $v_{s}$$v_{d}$$v_{i}$$v_{j}$
---
| $v_{s}$$v_{d}$$v_{i}$$v_{j}$
---
(d) | (e) |
Figure 12: reverse orientation of edges oriented by applying function $M_{1}$
or $M_{4}$

###### Lemma 34

Consider a graph $G=(\mathbf{V},\mathbf{E})$ with set of nodes $\mathbf{V}$
and set of edges $\mathbf{E}$. If we have $v_{i}\rightarrow v_{j}\in
DP[v_{k}\rightarrow v_{l}]$, we will have $v_{l}\rightarrow v_{k}\in
DP[v_{j}\rightarrow v_{i}]$.

Proof  First, we prove that this lemma holds for candidate sub-graphs for Meek
rule 1 and 4. Then, we extend this result for applying Meek function $M_{14}$
on a general graph. In Figure 12, the blue edges are oriented as the result of
applying Meek function on black edges. We depict the candidate sub-graph for
Meek rule 1 in the Figure 12(a). In this graph, the directed edge
$v_{s}\rightarrow v_{d}$ orients the edge $v_{d}\rightarrow v_{j}$. According
to Figure 12(b), if we orient the edge $v_{d}\rightarrow v_{j}$ in reverse
direction, i.e., $v_{j}\rightarrow v_{d}$, the edge $v_{s}\rightarrow v_{d}$
will be oriented in the reverse direction, i.e., $v_{d}\rightarrow v_{s}$.

The candidate sub-graph for Meek rule 4 is depicted in Figure 12(c). In this
sub-graph, by applying Meek function $M_{4}$, directed edge $v_{s}\rightarrow
v_{d}$ will orient two edges $v_{i}\rightarrow v_{j}$ and $v_{d}\rightarrow
v_{j}$. According to the graphs in Figure 12(d)(Figure 12(e)), if we orient
the edge $v_{d}\rightarrow v_{j}$($v_{i}\rightarrow v_{j}$) in reverse
direction, i.e., $v_{j}\rightarrow v_{d}$($v_{j}\rightarrow v_{i}$), the edge
$v_{s}\rightarrow v_{d}$ will be oriented in the reverse direction, i.e.,
$v_{d}\rightarrow v_{s}$. Hence, we proved that this lemma holds for candidate
sub-graphs of Meek function $M_{1}$ and $M_{4}$.

Based on the above observation, we will show the statement in the lemma holds
in a general graph. Assume we know $v_{i}\rightarrow v_{j}\in
DP[v_{k}\rightarrow v_{l}]$. The edge $v_{i}\rightarrow v_{j}$ has been
oriented in a repetitive sequence of applying Meek function $M_{1}$ and
$M_{4}$ in the corresponding candidate sub-graphs. Based on the above results,
we can reveres the sequence of applying Meek functions on each candidate sub-
graphs in order to orient the edge
$v_{l}\;\rule[1.72218pt]{8.99994pt}{0.5pt}\;v_{k}$ as $v_{l}\rightarrow
v_{k}$, and the proof is complete.

Based on the Lemma 33, if we show that the set of directed edges after
execution of Algorithm 6 is consistent, we can conclude no v-structure exists
in the output DAG. To do so, we prove following three facts: 1) The set of
directed edges as a result of applying Meek function $M_{124}$ in Line 5 is
consistent. 2) The set $\mathbf{S}$ is consistent with already directed edges.
3) The set $M_{124}({\mathbf{E}}_{\mathscr{G}}\sqcup\mathbf{S})$ is
consistent.

1) We prove this by induction on the number of steps taken by applying Meek
function $M_{124}$. For the base case, it is obvious that the edges in
$\mathbf{E}$ are consistent. For the induction step, suppose that the directed
edges up to step $r$ are consistent. We show that the directed edges will be
remained consistent after step $r+1$. We prove this by contradiction. Assume
that we orient new edge $v_{i}\rightarrow v_{j}$ in step $r+1$ by applying one
of the Meek functions and there exists an already directed edge
$v_{r}\rightarrow v_{t}$, such that for some edges
$v_{l}\;\rule[1.72218pt]{8.99994pt}{0.5pt}\;v_{k}\in\overline{\mathbf{E}}$ we
have $v_{l}\rightarrow v_{k}\in DP[v_{i}\rightarrow v_{j}]$, but
$v_{k}\rightarrow v_{l}\in DP[v_{r}\rightarrow v_{t}]$. Two cases can be
considered:

  * •

In the first case, we have: $v_{i}\rightarrow v_{j}\in M_{14}(\mathbf{E})$.
Thus, there exists an edge $v_{q}\rightarrow v_{w}$ such that
$v_{i}\rightarrow v_{j}\in DP[v_{q}\rightarrow v_{w}]$ and as a result
$v_{l}\rightarrow v_{k}\in DP[v_{q}\rightarrow v_{w}]$. This is a
contradiction, because we know the edges $v_{q}\rightarrow v_{w}$ and
$v_{r}\rightarrow v_{t}$ are consistent.

  * •

In this case, there exists a Meek rule 2 candidate sub-graph, such that we
have: $v_{i}\rightarrow v_{j}\in M_{2}(\\{v_{i}\rightarrow
v_{m},v_{m}\rightarrow
v_{j},v_{i}\;\rule[1.72218pt]{8.99994pt}{0.5pt}\;v_{j}\\})$. It can be shown
that if $v_{l}\rightarrow v_{k}\in DP[v_{i}\rightarrow v_{j}]$, we will have
$v_{l}\rightarrow v_{k}\in DP[v_{i}\rightarrow v_{m}]\sqcup
DP[v_{m}\rightarrow v_{j}]$ according to Property 4 in Lemma 12. This is a
contradiction, because the edges $v_{i}\rightarrow v_{m}$, $v_{m}\rightarrow
v_{j}$ and $v_{r}\rightarrow v_{t}$ are consistent.

2) In this case, we want to prove that the oriented edges in $\mathbf{S}$ are
consistent with already directed edges. We prove this by contradiction. Assume
we orient the edge $v\;\rule[1.72218pt]{8.99994pt}{0.5pt}\;v_{j}$ as
$v\rightarrow v_{j}$ in the procedure of orienting edges in $\mathbf{S}$ and
there exists an already directed edge $v_{r}\rightarrow v_{t}$, such that
$v_{l}\rightarrow v_{k}\in DP[v\rightarrow v_{j}]$ and $v_{k}\rightarrow
v_{l}\in DP[v_{r}\rightarrow v_{t}]$. Based on the Lemma 34, if we have
$v_{l}\rightarrow v_{k}\in DP[v\rightarrow v_{j}]$, we will have
$v_{j}\rightarrow v\in DP[v_{k}\rightarrow v_{l}]$. Having the relations
$v_{j}\rightarrow v\in DP[v_{k}\rightarrow v_{l}]$ and $v_{k}\rightarrow
v_{l}\in DP[v_{r}\rightarrow v_{t}]$,
$v_{j}\;\rule[1.72218pt]{8.99994pt}{0.5pt}\;v$ should be already oriented as
$v_{j}\rightarrow v$ when we apply Meek function $M_{124}$ in Line 5 and Line
9, which is a contradiction.

3) In part 2, we stated that the union of set $\mathbf{S}$ and set
${\mathbf{E}}_{\mathscr{G}}$ is consistent. Thus, based on part 1, oriented
edges as a result of applying Meek function $M_{124}$ on
${\mathbf{E}}_{\mathscr{G}}\sqcup\mathbf{E}$ is also consistent. Therefore,
the proof is complete.

Next, we will show that no cycle will be generated in the output graph
$\mathbf{E}_{\mathscr{G}}$ during the execution of Algorithm 6. In the
following lemma, we first prove that we do not have any directed cycle in this
graph if there is no directed cycle of length three.

###### Lemma 35

There is no directed cycle in a chordal graph if there exists no directed
cycle of length three in that chordal graph.

Proof  Given a graph $G=(\mathbf{V},\mathbf{E})$ with set of nodes
$\mathbf{V}$ and set of edges $\mathbf{E}$. Suppose there is a directed cycle
$(v_{1},...,v_{i},...,v_{j},...,v_{1})$ with length $N$ in graph $G$. Without
loss of generality, we assume that there is a chord between nodes $v_{i}$ and
$v_{j}$. Thus, based on the direction of edges between nodes $v_{i}$ and
$v_{j}$, we know one of the paths $(v_{1},...,v_{i},v_{j},...,v_{1})$ or
$(v_{i},...,v_{j},v_{i})$ will be a directed cycle with length less than $N$.
Thus, we can obtain a cycle with length less than $N$ from the original
directed cycle. We can repeat this procedure until end up with a directed
cycle of size three. Hence we can conclude that a cycle of size three exists
in a choral graph with directed cycle.

We know there is no cycle of length 3 in the set $\mathbf{E}$, and we will
show that no such cycle will be generated during the execution of Algorithm 6.
To do so, we need to prove three facts: 1) No cycle will be generated in Line
5. 2) No cycle will be generated during constructing $\mathbf{S}$ in Line 8.
3) No cycle will be created as the result of applying $M_{124}$ on
${\mathbf{E}}_{\mathscr{G}}\sqcup\mathbf{S}$. We will prove them in the
sequel.

Recall that the directed edges in $\mathbf{E}_{\mathscr{G}}$ remain consistent
during execution of Algorithm 6. We will use this statement in the following
proofs.

1) We prove this by induction on the number of steps taken by applying Meek
function $M_{124}$. For the base case, it is obvious that there is no cycle of
length three in the set $\mathbf{E}$. For the induction step, suppose that
there is no directed cycle of length three up to step $r$. We show that no
such a cycle will be generated in step $r+1$. We show this by contradiction.
First, consider Meek function $M_{2}$. Applying this function on a Meek
candidate sub-graph does not generate a cycle on that sub-graph. Therefore, we
only consider the case in which the oriented edge as the result of applying
Meek function $M_{2}$ in a candidate sub-graph makes cycle in another sub-
graph. In that case we will have the following structure as
$\\{v_{i}\rightarrow v_{j},v_{j}\rightarrow v_{k},v_{k}\rightarrow
v_{l},v_{l}\rightarrow
v_{i},v_{j}\;\rule[1.72218pt]{8.99994pt}{0.5pt}\;v_{l}\\}$. In such sub-graph,
we have $v_{l}\rightarrow v_{k}\in DP[v_{i}\rightarrow v_{j}]$. This means the
mentioned orientations violates the consistency, which is a contradiction.

The all sub-graphs that are able to make a new cycle after applying Meek
function $M_{1}$ or $M_{4}$ are depicted in Table 7. We check each of these
cases and show that none of them can make a cycle. Case 1 and 2 belong to Meek
function $M_{1}$, and the remaining two cases are for Meek function $M_{4}$.
Black edges are already oriented and the red edge is the one that applying
specific Meek function on that edge will orient green edges. We intend to
check whether the green edge makes a cycle or not. As the first case violates
the consistency, it cannot be happened. In case 2, no cycle is generated. In
case 3, similar to case 1, the consistency is violated. Finally, no cycle will
be generated in case 4.

Table 7: Different cases that make cycle after applying Meek function $M_{1}$ or $M_{4}$ Case 1 | Case 2 | Case 3 | Case 4
---|---|---|---
Meek function $M_{1}$ | Meek function $M_{4}$
$v_{1}$$v_{4}$$v_{2}$$v_{3}$ | $v_{1}$$v_{4}$$v_{2}$$v_{3}$ | $v_{1}$$v_{4}$$v_{2}$$v_{3}$ | $v_{1}$$v_{4}$$v_{2}$$v_{3}$

2) In this case, we orient some edges connected to node $v$. Thus, for making
a cycle $C$ by orienting some edges during the $\mathbf{S}$ construction, two
case can be considered. In addition of already directed edges, one (the first
case) or two (the second case) edges are oriented in $C$ in the procedure of
$\mathbf{S}$ construction. The first case cannot be occurred because it means
we have a Meek candidate sub-graph $M_{2}$ while the Meek functions $M_{124}$
in Line 5 or Line 9 has already been applied. In the second case, if both
edges are oriented, they are out-going edges and cannot make a cycle.

3) In this part, we prove that the set of directed edges in the result of
applying Meek function $M_{124}$ on
$\mathbf{S}\sqcup{\mathbf{E}}_{\mathscr{G}}$ cannot generate a cycle. To do
so, we recall from part 1 that applying Meek function $M_{124}$ on a set with
the consistent directed edges cannot make a cycle. As we showed, the union of
set $\mathbf{S}$ and set ${\mathbf{E}}_{\mathscr{G}}$ is consistent, no cycle
exists in the result of applying Meek function $M_{124}$ on this set.

All in all, we proved that for any $\mathbf{E}$ as an input that is satisfying
our assumptions, the set of directed edges after each iteration of the
algorithm are subset or equal of a causal DAG in true MEC. As the number of
edges are finite, the algorithm terminates and return a causal DAG in true MEC
and the proof is complete.

## References

  * Agrawal et al. (2019) Raj Agrawal, Chandler Squires, Karren Yang, Karthikeyan Shanmugam, and Caroline Uhler.  Abcd-strategy: Budgeted experimental design for targeted causal structure discovery.  _Proceedings of Machine Learning Research_ , 89, 2019.
  * Andersson et al. (1997) Steen A. Andersson, David Madigan, and Michael D. Perlman.  A characterization of markov equivalence classes for acyclic digraphs.  _Annals of Statistics_ , 25(2):505–541, 1997\.
  * Brown et al. (2005) Laura E. Brown, Ioannis Tsamardinos, and Constantin F. Aliferis.  A comparison of novel and state-of-the-art polynomial bayesian network learning algorithms.  _Proceedings of the $20^{t}h$ National Conference on Artificial Intelligence_, page pp.739–745, 2005.
  * Chickering (1995) David Maxwell Chickering.  A transformational characterization of equivalent bayesian-network structures.  _Proceedings of Eleventh Conference on Uncertainty in Artificial intelligence, Montreal, QU_ , pages pages 87–98, 1995.
  * Eberhardt et al. (2005) Frederick Eberhardt, Clark Glymour, and Richard Scheines.  On the number of experiments sufficient and in the worst case necessary to identify all causal relations among n variables.  _Proceedings of the 21st Conference on Uncertainty in Artificial Intelligence (UAI)_ , page 178–184, 2005.
  * Eigenmann et al. (2017) Marco F Eigenmann, Preetam Nandy, and Marloes H Maathuis.  Structure learning of linear gaussian structural equation models with weak edges.  _arXiv preprint arXiv:1707.07560_ , 2017.
  * Ghassami et al. (2018) AmirEmad Ghassami, Saber Salehkaleybar, Negar Kiyavash, and Elias Bareinboim.  Budgeted experiment design for causal structure learning.  _International Conference on Machine Learning_ , page 1724–1733, 2018.
  * Ghassami et al. (2019) AmirEmad Ghassami, Saber Salehkaleybar, Negar Kiyavash, and Kun Zhang.  Counting and sampling from markov equivalent dags using clique trees.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 33:3664–3671, Jul 2019.
  * Greenewald et al. (2019) Kristjan Greenewald, Dmitriy Katz, Karthikeyan Shanmugam, Sara Magliacane, Murat Kocaoglu, Enric Boix-Adsera, and Guy Bresler.  Sample efficient active learning of causal trees.  _33rd Conference on Neural Information Processing Systems (NeurIPS)_ , 2019.
  * Hauser and Buhlmann (2012) Alain Hauser and Peter Buhlmann.  Characterization and greedy learning of interventional markov equivalence classes of directed acyclic graphs.  _Journal of Machine Learning Research_ , 13(1):2409–2464, August 2012.
  * Hauser and Buhlmann (2014) Alain Hauser and Peter Buhlmann.  Two optimal strategies for active learning of causal models from interventional data.  _International Journal of Approximate Reasoning_ , 55(4):926–939, Jun 2014.
  * He and Geng (2008) Yangbo He and Zhi Geng.  Active learning of causal networks with intervention experiments and optimal designs.  _The Journal of Machine Learning Research_ , 9(Nov):2523–2547, 2008.
  * He and Yu (2016) Yangbo He and Bin Yu.  Formulas for counting the sizes of markov equivalence classes of directed acyclic graphs.  _arXiv preprint arXiv:1610.07921_ , 2016.
  * He et al. (2015) Yangbo He, Jinzhu Jia, and Bin Yu.  Counting and exploring sizes of markov equivalence classes of directed acyclic graphs.  _The Journal of Machine Learning Research_ , 16(1):2589–2609, 2015.
  * Hoyer et al. (2012) Patrik O Hoyer, Aapo Hyvarinen, Richard Scheines, Peter L Spirtes, Joseph Ramsey, Gustavo Lacerda, and Shohei Shimizu.  Causal discovery of linear acyclic models with arbitrary distributions.  _arXiv preprint arXiv:1206.3260_ , 2012.
  * Kalisch et al. (2012) Markus Kalisch, Martin Machler, Diego Colombo, Marloes H. Maathuis, and Peter Bühlmann.  Causal inference using graphical models with the R package pcalg.  _Journal of Statistical Software_ , 47(11):1–26, 2012.  URL https://www.jstatsoft.org/article/view/v047i11.
  * Kocaoglu et al. (2017) Murat Kocaoglu, Alex Dimakis, and Sriram Vishwanath.  Cost-optimal learning of causal graphs.  _In International Conference on Machine Learning_ , 2017.
  * Maathuis et al. (2009) Marloes H. Maathuis, Markus Kalisch, and Peter Buhlmann.  Estimating high-dimensional intervention effects from observational data.  _The Annals of Statistics_ , page 37(6A):3133–3164, 2009.
  * Markenzon et al. (2008) Lilian Markenzon, Oswaldo Vernet, and Luiz Henrique Araujo.  Two methods for the generation of chordal graphs.  _Ann. of Op. Res._ , 157(1):47–60, 2008.
  * Meek (1995) Christopher Meek.  Causal inference and causal explanation with background knowledge.  _Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence_ , page 403–410, 1995.
  * Ness et al. (2017) Robert O Ness, Karen Sachs, Parag Mallick, and Olga Vitek.  A bayesian active learning experimental design for inferring signaling networks.  _In International Conference on Research in Computational Molecular Biology, Springer_ , page 134–156, 2017.
  * Pearl (2009) Judea Pearl.  _Causality_.  Cambridge university press, 2009.
  * Peters et al. (2017) Jonas Peters, Dominik Janzing, and Bernhard Scholkopf.  Elements of causal inference: foundations and learning algorithms.  _MIT press_ , 2017.
  * Ramsey et al. (2017) Joseph Ramsey, Madelyn Glymour, Ruben Sanchez-Romero, and Clark Glymour.  A million variables and more: the fast greedy equivalence search algorithm for learning high-dimensional graphical causal models, with an application to functional magnetic resonance images.  _International Journal of Data Science and Analytics_ , page pages 1–9, 2017.
  * Rose (1970) Donald J. Rose.  Triangulated graphs and the elimination process.  _J. Math. Anal. Appl._ , page 597–609, 1970.
  * Rothenhausler et al. (2018) Dominik Rothenhausler, Jan Ernest, and Peter Buhlmann.  Causal inference in partially linear structural equation models: identifiability and estimation.  _Ann. Stat. To appear_ , 2018.
  * Shanmugam et al. (2015) Karthikeyan Shanmugam, Murat Kocaoglu, Alexandros, G. Dimakis, and Sriram Vishwanath.  Learning causal graphs with small interventions.  _In Advances in Neural Information Processing Systems_ , page 3195–3203, 2015.
  * Spirtes et al. (2000) Peter Spirtes, Clark Glymour, and Richard Scheines.  _Causation, prediction, and search._ MIT press, 2000.
  * Talvitie and Koivisto (2019) Topi Talvitie and Mikko Koivisto.  Counting and sampling markov equivalent directed acyclic graphs.  _In The Thirty-Third AAAI Conference on Artificial Intelligence_ , 9(Nov):7984–7991, 2019.
  * Teshnizi et al. (2020) Ali Ahmadi Teshnizi, Saber Salehkaleybar, and Negar Kiyavash.  Lazyiter: A fast algorithm for counting markov equivalent dags and designing experiments.  _In International Conference on Machine Learning_ , page 1663–1671, 2020.
  * Verma and Pearl (1992) Thomas Verma and Judea Pearl.  An algorithm for deciding if a set of observed independencies has a causal explanation.  _Uncertainty in Artificial Intelligence_ , pages 323–330, 1992.
  * Wang et al. (2017) Yuhao Wang, Liam Solus, Karren Yang, and Caroline Uhler.  Permutation-based causal inference algorithms with interventions.  _In Advances in Neural Information Processing Systems_ , page 5822–5831, 2017.