Take the 2-minute tour ×
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.

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?

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
    
If the original DAG is simple, you won't get self-loops (since the OP specified that the chosen edge is removed). –  Ilmari Karonen Jan 15 '13 at 12:20
1  
Depending on how exactly you define the contraction, you might end up with a non-simple graph in the process, even if the original graph is simple. Consider $D=(V,A)$ with $V={1,2,3}$ and $A={(1,2),(2,3),(1,3)}$. Contracting (1,2) will give you a non-simple graph and another contraction a self-loop. Of course, requiring that intermediate graphs also have to be simple by removing multiple occurences of the same arc will leave you free of self-loops –  user58346 Jan 15 '13 at 13:06

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.