Weaker notion of topological ordering for directed graphs

Question

Let $G = (V,E)$ be a directed graph with $v \rightarrow w$ denoting an edge from $v$ to $w$. Now if $\le$ is a total order on $V$ then $\le$ is called topological order of $G$ if $v \rightarrow w$ implies $v \le w$ for any $(v,w)$ in $V \times V$. It also known that such a topological order of $G$ exists iff $G$ is a DAG (directed acyclic graph).

I am interested in the following weaker notion of topological order: Let $\le$ be a partial order (not necessarily total) on $V$. Then lets call $\le$ a weak topological order of $G$ if for any $(v,w)\in V \times V$ the relation $v \rightarrow w$ implies that $v \le w$ or that $v$ and $w$ are incomparable.

It is easy to see that such a weak topological order (WTO) also exists for graphs with cycles. It is also clear that such a WTO cannot be unique (the order where all elements all incomparable is always a WTO). However I also suspect that there is a some notion of 'maximal' WTO in the sense that it has the least number of incomparable pairs.

Is anyone aware that this notion of 'weak topological order' has been studied systematically? I would be grateful for any references.

Answer 1

This is a combination of common constructions.

First define a preorder $\le^1$ such that $v\le^1 w$ if and only if there is a directed path in the graph from $v$ to $w$. $\le^1$ has the properties

• $v\le^1 v$
• $u\le^1 v$ and $v\le^1 w$ implies $u\le^1 w$

It's called a preorder because it's possible that $v\le^1 w$ and $w\le^1 v$ both hold even when $v\ne w$. This happens if and only if $v,w$ are contained in a cycle.

A preorder defines an equivalence relation $v\equiv^1 w$ if and only if $v\le^1 w$ and $w\le^1 v$. The next step is to take a quotient of the set by this equivalence relation $\equiv^1$ and define a quotient order $\le^2$ on the quotient set $[v]\le^2[w]\leftrightarrow v\le^1 w$ which is a partial order.

What you want to do is instead of taking quotient, order each equivalence class $\equiv^1$ internally in an arbitrary fashion. However, since the elements of each equivalence class participate in a cycle, you can't order them internally in any way that keeps the anti-symmetry property of a partial order unless you leave them all incomparable. So I think that's it. Leave each equivalence class incomparable internally, but sustain the order $\le^1$ between different equivalence classes.