Given a DAG, is it always possible to find an edge such that if that edge is removed and the start and end nodes of the edge merged, the result is another DAG?
Tell me more
×
Mathematics Stack Exchange is a question and answer site for
people studying math at any level and professionals in related fields. It's 100% free, no registration required.
|
|
|
Yes! In order to see this, consider a topological ordering $v_1,\ldots, v_n$ of the DAG and the arc $(v_1,v_i)$, where $v_i$, $2\leq i \leq n$, is the first node for which an arc starting from $v_1$ exists. edit: note that you might end up with self-loops, i considered these cases to not be relevant. |
|||||||
|
|
As pm notes, if the DAG is finite (and has at least one edge), the answer is yes. To see this, note that the transitive closure of the edges of a DAG is a partial order on the nodes. Pick any node $x$ which has at least one edge leading away from it, and consider the set $Y$ of nodes having an edge from $x$. As $Y$ is a finite subset of a partially ordered set, it has at least one minimal element $y$. Since $y$ is a minimal element of $Y$, it follows that there is no indirect path from $x$ to $y$, since any such path would have to pass through some other node $y' \in Y \setminus \{y\}$. Thus, removing the edge $(x,y)$ and merging $x$ and $y$ cannot introduce any cycles. For infinite DAGs, this is not necessarily true. As a counterexample, consider the infinite DAG whose nodes are the rational numbers and there is an edge from $x$ to $y$ iff $x < y$. Then, for any two nodes $x < y$, there exists an indirect path from $x$ to $y$ via the node $(x+y) / 2$, and thus merging $x$ and $y$ would introduce a cycle. |
||||
|
|
