Getting all vertices with fixed index in their topological ordering of a DAG

Question

During my self study for graphs, I'm currently learning about topological sorting and ran into a question I'm not sure how to solve.

There are typically more than one order of a topological ordering for any given DAG. Some vertices will always be in the same index regardless of the ordering. Find a linear algorithm to get all fixed vertices in the topological order for a DAG.

From what I've gathered, this means that that fixed vertex is related to all vertices after it in the ordering AND it depends on all vertices before it in the ordering.

I've been trying to work out a linear algorithm to get all of these vertices but I'm not sure how.

Answer 1

In my discussion, I will assume that the $|V|$ vertices of the DAG are represented as integers $0,1,..., |V|-1$ so they can be used as indices of an array. In case, different "labeling" is used, all arrays used in the solution can be replaced by any dictionary structure. Also, it is assumed that the DAG is represented as an adjacency list.

Idea

The idea behind the algorithm below is based on the observation that if vertex $v$ is the only source (a vertex with no incoming edge) in the DAG then $v$'s position must be fixed in the topological sort. Now, removing $v$ and all its out-going edges from the DAG might create 0 or more sources. If in case only one new source is created, then this new source has fixed position too. If multiple sources are created, then all these new sources cannot have fixed position, since their order with respect to each other can be arbitrary. You just have to repeat this process until all vertices are classified and removed. However, if in case a newly created source $v'$ is also a sink (a vertex with no outgoing edge), then any remaining vertex $u$ in the graph cannot have a fixed position since $v'$ can appear before or after $u$ in the topological order.

Algorithm

The algorithm can be viewed as BFS-based topological sorting algorithm. Let $I$ be an array containing the number of incoming edges of each vertex $v$. Let $Q$ be the queue. Then, let $F$ be a Boolean array, initially filled with false values, that will be used to set the mark of a vertex whether it has fixed position or not, e.g. $F[v]$ is true if vertex $v$ has fixed position. Finally, let $sinked$ be a Boolean variable, initially false, that will indicate if a source that is also a sink has been found. The algorithm is as follows:

1. Fill $I$ with values by scanning the adjacency list of the DAG.
2. Scan $I$ to find the sources, e.g. vertices whose value in $I$ is 0. When a source is found, insert it to $Q$.
3. Let $s$ be the number of vertices in $Q$. Repeat the following $s$ times:
   1. Remove a vertex $v$ from $Q$.
   2. If $s > 1$ or $sinked$ is true, set $F[v]$ to false.
   3. If $v$ is a sink, set $sinked$ to true.
   4. For each neighbor $u$ of $v$ in the DAG, decrement $I[u]$ by 1. If after this, $I[u]$ becomes 0, insert $u$ to $Q$.
4. If $Q$ is not empty, repeat step 3, otherwise scan $F$ to find all vertices marked as fixed (set to true).

Analysis

Step 1 of the algorithm can be performed in $O(|V|+|E|)$ time. Step two takes $O(|V|)$ time. While the remaining part is just BFS, with the modification that a vertex will only be added to $Q$ if it's a source. This is equivalent to adding a vertex, the last time it was found during BFS, which unlike the usual case where the vertex is added the first time it was found. Since BFS takes $O(|V|+|E|)$ time, the entire algorithm takes $O(|V|+|E|)$ time, which is linear.

Note

This algorithm is a modification of Kahn's Topological sorting algorithm.