7
$\begingroup$

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 ?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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