A procedure for Topological sort, proof for its correctness

Question

Definition: A preserved invariant of a state machine is a predicate, $P$, on states, such that whenever $P(q)$ is true of a state, $q$, and $q \rightarrow r$ for some state, $r$, then $P(r)$ holds.

Definition: A line graph is a graph whose edges are all on one path.

Definition: Formally, a state machine is nothing more than a binary relation on a set, except that the elements of the set are called “states,” the relation is called the transition relation, and an arrow in the graph of the transition relation is called a transition. A transition from state $q$ to state $r$ will be written $q \rightarrow r$.

DAG: Directed Acylic Graph

The following procedure can be applied to any directed graph, $G$:

1. Delete an edge that is in a cycle.
2. Delete edge $<u \rightarrow v>$ if there is a path from vertex $u$ to vertex $v$ that does not include $<u \rightarrow v>$.
3. Add edge $<u \rightarrow v>$ if there is no path in either direction between vertex $u$ and vertex $v$.

Repeat these operations until none of them are applicable.

This procedure can be modeled as a state machine. The start state is $G$, and the states are all possible digraphs with the same vertices as $G$.

(b) Prove that if the procedure terminates with a digraph, $H$, then $H$ is a line graph with the same vertices as $G$.

Hint: Show that if $H$ is not a line graph, then some operation must be applicable.

(c) Prove that being a DAG is a preserved invariant of the procedure.

(d) Prove that if $G$ is a DAG and the procedure terminates, then the walk relation of the final line graph is a topological sort of $G$.

Hint: Verify that the predicate $P(u,v)$:: there is a directed path from $u$ to $v$ is a preserved invariant of the procedure, for any two vertices $u, \ v$ of a DAG.

(e) Prove that if $G$ is finite, then the procedure terminates.

Hint: Let $s$ be the number of cycles, $e$ be the number of edges, and $p$ be the number of pairs of vertices with a directed path (in either direction) between them. Note that $p \leq n^2$ where $n$ is the number of vertices of $G$. Find coefficients $a,b,c$ such that as+bp+e+c is nonnegative integer valued and decreases at each transition.

My Problems:

I got stuck with problems $d$ and $e$ but solutions to other problems are welcome too.

At problem $d$, I could not understand the hint and why it is given, how it helps.

In my way for proving $d$, I am trying to show that given procedure always preserves the order of vertices, which are associated with edges, on the start graph $G$. So a line graph is automatically a topological sort since the "precedence order" of the vertices are preserved.

But procedure number $3$ is problematic, how to show it preserves precedence ?

Answer 1

b. As operation $1$ cannot be performed, $H$ must be a DAG. Consider a topological sort of $H$. As $3$ cannot be performed, if $u$ precedes $v$ in the topological sort, there is a path from $u$ to $v$. Start at the initial vertex in the sort and keep moving forward until we find a vertex which has more than one outgoing edges (if each vertex has only one outgoing, then it is a line graph). Let $u$ have edges to $v$ and $w$ and let $v$ precede $w$. Then there is path from $v$ to $w$, which gives a path from $u$ to $w$ that doesn't include $u \rightarrow w$, a contradiction as operation $2$ can be performed here.

c. As deleting edges will not alter DAG property, we only need to check $3$. A cycle is formed only when we add an edge $u \rightarrow v$, when there was a path from $v$ to $u$ already. As $3$ doesn't add such edges, DAG is maintained.

d. Let $H$ be obtained from $G$ by a single operation. We show that any topological sort of $H$ is also valid for $G$ (note that the converse need not be true). For this we need to show that if there was a path from $u$ to $v$ in $G$, then there is path from $u$ to $v$ in $H$ too. Some path can be broken only when we are removing edges. So clearly operation $3$ will not cause any problem here. Also, in $2$, we are only removing those edges $u \rightarrow v$ where there is already a path from $u$ to $v$. So for any path from $w$ to $z$, containing that edge, we can just replace that edge by the path from $u$ to $v$, maintaining a path from $w$ to $z$ in $H$. And $G$ is DAG, so $1$ never happens.

e. First observe how each of $s$, $e$ and $p$ change with each operation. With operation $1$, $s$ reduces by at least $1$, $e$ reduces by $1$ and $p$ can decrease by close to $n^2$ (almost all paths might be broken). With $2$, $s$ might reduce by $1$ (not necessary though), $e$ reduces by $1$ and $p$ is unchanged. With $3$, $s$ doesn't change, $e$ increases by $1$ and $p$ increases by at least $1$. Notice that as we are going towards line graph, we are trying to reduce number of edges ($e$), remove cycles ($s$) while increasing $p$. So in $as+bp+de+c$, we expect $a$ and $d$ to be positive and $b$ to be negative. The worst case changes in $s,e,p$ for each operation are

$$ \begin{array}{cccc} & s & e & p \\ 1. & -1 & -1 & -n^2 \\ 2. & 0 & -1 & 0 \\ 3. & 0 & 1 & 1 \end{array} $$

As $s$ never increases, we can make $a$ as large as we want. As we can scale $a,b,d$ by a constant, lets keep $d=1$. With these observations we can get one possible set of values for $a,b,d$ as $2n^2$, $-2$ and $1$ respectively. And pick $c$ as negative of the value at line graph.