Deleting Edges

The other basic operator, the removal of an edge (either link or arc) is much simpler than the addition of an edge, since only one neighboring configuration is obtained when we delete an edge. Moreover, it is not necessary to perform any test for detecting directed or undirected cycles. However, in this case we need to preserve condition 4 in the definition of RPDAG (if $x\rightarrow y$ exists in $G \Rightarrow \vert Pa_G(y)\vert\geq 2$ or $Pa_G(x)\neq\emptyset$), that could be violated after an arc is deleted. This situation may appear only when we are going to remove an arc $x\rightarrow y$ and either $Pa_G(y)=\{x\}$ or $Pa_G(y)=\{x,u\}$: in the first case, all the children of $y$ that do not have other parents than $y$ must be converted into neighbors of $y$, and this process is repeated starting from each of these children; in the second case, if $Pa_G(u)=\emptyset$ then in addition to the previous process, the arc $u\rightarrow y$ must be converted into the link $u\mbox{-}y$. Figure 13 illustrates these situations. This procedure of transforming arcs into links is exactly the same as the one described in the proof of Proposition 2.

Figure 13: Transforming arcs into links after removing the arc $x\rightarrow y$

Figure 14: For each state of the decision tree in Fig. 10, an example of the neighboring configurations of an RPDAG that can be obtained after adding an edge between nodes $x$ and $y$