The Operators

Although the previous description of the operators that define the neighborhood of an RPDAG is quite convenient from a practical (implementation) point of view, for the sake of clarity, we shall describe them in another way. In fact, we shall use five operators:

• $A\_arc(x,y)$, addition of an arc $x\rightarrow y$.
• $A\_link(x,y)$, addition of a link $x\mbox{-}y$.
• $D\_arc(x,y)$, deletion of an arc $x\rightarrow y$.
• $D\_link(x,y)$, deletion of a link $x\mbox{-}y$.
• $A\_hh(x,y,z)$, addition of an arc $x\rightarrow y$ and creation of the h-h pattern $x\rightarrow y\leftarrow z$ by transforming the link $y\mbox{-}z$ into the arc $y \leftarrow z$.

The conditions that the current RPDAG $G$ must verify so that each of these operators can be applied in order to obtain a valid neighboring RPDAG are shown in Table 2. These conditions can be easily derived from the information in Figure 10 and Table 1. In Table 2, $UC(x\mbox{-}y)$ represents a test for detecting completely undirected cycles after inserting the link $x\mbox{-}y$ in the current RPDAG. Note that we can perform this test very easily without actually inserting the link: it is only necessary to check the existence of a path between $x$ and $y$ exclusively formed by the links. Similarly, $DC(x\rightarrow y)$ and $DC(x\rightarrow y\leftarrow z)$ represent tests for detecting directed cycles after inserting the arc $x\rightarrow y$ and the h-h pattern $x\rightarrow y\leftarrow z$ in the current RPDAG, respectively (and perhaps completing). It should also be noted that we can perform these tests without inserting the arc or the h-h pattern: in this case we only need to check the existence of a path from $y$ to $x$ containing only either links or arcs directed away from $y$ (a partially directed path from $y$ to $x$). Table 2 also shows which operators may require a post-processing step in order to ensure that the corresponding neighboring configuration of $G$ is an RPDAG. In Table 2, $Complete(y)$ and $Undo(y)$ refer to the procedures that preserve conditions 1 and 4 in Definition 1, respectively. Note that both $UC(x\mbox{-}y)$ and $Complete(y)$ take time $O(l_y)$ in the worst case, where $l_y$ is the number of links in the subgraph induced by the chain component of $G$ that contains $y$; $Undo(y)$ takes time $O(d_y)$ in the worst case, where $d_y$ is the number of arcs in the subgraph induced by the set of descendants of $y$ in $G$ that only have one parent; $DC(x\rightarrow y)$ and $DC(x\rightarrow y\leftarrow z)$ both take time $O(dl_y)$ in the worst case, where $dl_y$ is the number of edges (either arcs or links) in the subgraph induced by the nodes in the chain component of $G$ that contains $y$ together with their descendants.

Table 2: The operators, their conditions of applicability, and post-processing requirements

Operator	Conditions	Post-processing
	$x\not\in Ad_G(y)$; $p_G(x)\neq 0$ or $p_G(y)\neq 0$;	if $p_G(x)\neq 0 \mbox{ {\small and} } n_G(y)\neq 0$
$A\_arc(x,y)$	if $\left( p_G(x)\neq 0 \mbox{ {\small and} } (c_G(y)\neq 0 \mbox{ {\small or} } n_G(y)\neq 0)\right)$	then $Complete(y)$
	then $DC(x\rightarrow y)=False$
	$x\not\in Ad_G(y)$; $p_G(x)=0$ and $p_G(y)=0$;
$A\_link(x,y)$	if $\left(n_G(x)\neq 0 \mbox{ {\small and} } n_G(y)\neq 0\right)$	None
	then $UC(x\mbox{-}y)=False$
$D\_arc(x,y)$	$x\in Pa_G(y)$	if $p_G(y)\leq 2$
		then $Undo(y)$
$D\_link(x,y)$	$x\in Ne_G(y)$	None
	$x\not\in Ad_G(y)$; $z\in Ne_G(y)$;
$A\_hh(x,y,z)$	$p_G(y)=0$ and $n_G(y)\neq 0$;	if $n_G(y)\geq 2$
	if $\left(n_G(y)\geq 2 \mbox{ {\small and} } (p_G(x)\neq 0 \mbox{ {\small or} } n_G(x)\neq 0\right)$)	then $Complete(y)$
	then $DC(x\rightarrow y\leftarrow z)=False$