Overview

Our basic operators are the inclusion of an edge between a pair of non-adjacent nodes and the removal of an existing edge between a pair of adjacent nodes in the current configuration. These edges may be either directed or undirected.

The inclusion of an isolated link $x\mbox{-}y$ will serve as a template for the arcs $x\rightarrow y$ and $x\leftarrow y$; however, the link $x\mbox{-}y$ together with another link $x\mbox{-}z$ represent any combination of arcs except those that create new h-h patterns (the DAGs (a), (b) and (c) in Figure 3). In the case of adding an arc, we may obtain several different neighboring configurations, depending on the topology of the current RPDAG and the direction of the arc being included. As we will see, if we are testing the inclusion of an edge between two nodes $x$ and $y$, this may involve testing some of the different valid configurations obtained by the inclusion of the link $x\mbox{-}y$, the arc $x\rightarrow y$, the arc $x\leftarrow y$, the h-h pattern $x\rightarrow y\leftarrow z$ or the h-h pattern $z\rightarrow x\leftarrow y$ (where $z$ in the last two cases would be any node such that either the link $y\mbox{-}z$ or the link $z\mbox{-}x$ exists in the current configuration). However, the removal of an edge will always result in only one neighboring configuration. Other operators, such as arc reversal [16], will not be used by our search method. The set of neighboring configurations of a given RPDAG $G$ will therefore be the set of all the different RPDAGs obtained from $G$ by adding or deleting a single edge (either directed or undirected).

Before explaining the details of the search method, let us illustrate the main ideas by means of the following example: consider the RPDAG in Figure 8, which represents the current configuration of the search process (this figure only displays the part of the RPDAG corresponding to the neighborhood of the nodes $x$ and $y$), and assume that we shall include an edge between the nodes $x$ and $y$.

Figure 8: Node $x$ has one parent and one child, $y$ does not have any parents and has two neighbors

In this situation, we cannot introduce the link $x\mbox{-}y$ because we would violate one of the conditions defining RPDAGs (condition 1). We may introduce the arc $x\rightarrow y$ and in this case, again in order to preserve condition 1, the two neighbors of $y$ must be converted into children. We can also include the arc $x\leftarrow y$. Finally, we may include two different h-h patterns $x\rightarrow y\leftarrow z$, where $z$ is a neighbor of $y$ (the other neighbor must be converted into a child, once again in order to preserve condition 1). These four different configurations are displayed in Figure 9.

Figure 9: Neighboring configurations obtained by including an edge between $x$ and $y$ in the configuration of Fig. 8