1
$\begingroup$

Let $G$ be a DAG with $v \in V$. Suppose that there exists some $i$ such that for all topological orderings $v_1, \ldots, v_n$ we have $v_i = v$.

What's a set of necessary and sufficient conditions about $v$ for this to occur?

$\endgroup$
  • 1
    $\begingroup$ What do you think? Can you come up with any necessary and sufficient conditions? How about for specific $i$? $\endgroup$ – Yuval Filmus Mar 13 '17 at 8:59
  • $\begingroup$ Hint: Suppose $v=v_i$ for all topological orderings of $G$. Then how does the set $\{v_1,\ldots,v_{i-1}\}$ change between topological orderings? $\endgroup$ – Klaus Draeger Mar 13 '17 at 13:13
2
$\begingroup$

Theorem: A given vertex $v$ always comes first, $i = 1$, iff it has no incoming edges and every other vertex has at least one incoming edge.

Right-to-left implication: no vertex other than $v$ can come first, since they all have incoming edges.

Left-to-right: for $v$ to come first it has to have in-degree 0. If some vertex $w$ has in-degree 0 with $w \neq v$ and there's a topological ordering where $w$ has a left neighbour $u$, then swapping $w$ and $u$ yields another topological ordering: the only vertices which have new relative positions are $u$ and $w$, and since $w$ has in-degree 0 no constraint is violated by putting it before $u$.

Repeatedly move the leftmost such $w$ one step to the left; this will end when one such $w$ comes first, contradicting the assumption that $v$ always comes first. Hence no $w$ exists.

QED

By a symmetric argument, a vertex always comes last if it alone has out-degree 0.

Theorem: $v$ is fixed-index iff it is comparable to every other vertex (i.e. for all $w$, either $w = v$ or there is a path from $v$ to $w$ or there is a path from $w$ to $v$).

Right-to-left: compare $v$ to all other vertices. All $w$ with a path to $v$ must come before $v$ and all $u$ with a path from $v$ to $u$ must come after $v$. That leaves only one index at which $v$ can occur.

Left-to-right: assume for the sake of contradiction that there exists some $w$ to the left of $v = v_j$ in some topological ordering, where $w$ is incomparable to $v$, i.e. there is neither a path from $v$ to $w$ nor from $w$ to $v$. Let $u = v_i$ be the rightmost among those, $i < j$.

Consider $t = v_{i+1}$. By $u$ being the rightmost incomparable vertex left of $v$, either $t = v$ or $t < v$. If $u$ were comparable to $t$ then $u$ would also be comparable to $v$ (by transitivity through $t$) so it isn't. Hence we can swap $u$ and $t$ and remain topologically ordered. Continue doing this until $u$ and $v$ get swapped, contradicting $v$ being fixed-index.

Similarly derive a contradiction from the existence of an incomparable vertex to the right of $v$. Hence there is no incomparable vertex.

QED

Some consequences:

Let a digraph $G$ be Weakly Connected if the undirected counterpart is connected; define Weakly Connected Components analogously.

Any interleaving of the topological orderings of two weakly connected components is a topological ordering of their union. In particular, one can put the entire ordering of one component immediately before or after a given vertex in the other component, so no vertex can be fixed-index (so long as both components are non-empty).

Corollary: a DAG with a fixed-index vertex is weakly connected.

A more direct and constructive proof: $path(s, v) + path(v, t) = path(s, t)$ where the precise definition of $path$ and $+$ is left as an exercise ;-)

There is no implication in the other direction: consider the complete bipartite graph on 2+2 vertices, edges left-to right, with $a, b$ on the left and $c, d$ on the right; then $a$ and $b$ come before $c$ and $d$, but $a$ and $b$ can always be swapped, and so can $c$ and $d$. This graph is weakly connected but has no fixed-index vertex.

It is also not the case that all paths from $v_i$ to $v_k$ go through $v = v_j$ when $i < j < k$. For (counter)example, $V = \{a, b, c\}$ and $E = \{(a, b), (a, c), (b, c)\}$ which has only one topological ordering. Let $(v_i, v, v_k) = (a, b, c)$; then there is a path of length 1 from $a$ to $c$ which doesn't go through $b$.

$\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.