1
$\begingroup$

I'm reading Algorithm Design by Jon Kleinberg. In section 3.6, in order to compute the topological ordering of a DAG, one first finds a root node in this DAG, then deletes it from the DAG. The author claimed that this can be done in $O(n)$.

How should I understand this time complexity? Just because we traverse all nodes in $O(n)$? But in the iteration for some node $v$, one also needs to traverse all its incident edges. Does that mean the time complexity should be $O(m+n)$ or $O(m)$? Is it related to the data structure which one uses to represent the DAG?

$\endgroup$
  • $\begingroup$ In all common implementations of a graph, you will have direct access to in and out-degree of a node, so you don't need to traverse the edges individually. But even if you don't, you can augment your data structure s.t. you add/update in/out-degrees while you're constructing the graph. $\endgroup$ – Ameer Jewdaki Nov 28 '19 at 11:42
1
$\begingroup$

It certainly depends on the data structure used to represent the DAG.

We will use a data structure that I am going to call the characteristic-hash-vector (CHV). Given a graph $G$ of size $n$, and a subgraph $S \subseteq G$, the characteristic vector $X_S$ is the vector of size $n$ that has a 1 for each node in $S$ and a 0 for all other elements. The CHV is a way of representing the characteristic vector using a hashmap. Given a subset $S$, each node $v$ in $G$ is mapped to $X_S(v)$.

Let's try representing the DAG as a set of nodes, and with each node $x$, maintain a CHV for incoming nodes $y$ (there exists a directed edge from $y$ to $x$) and a CHV for outgoing nodes $w$ (there exists a directed edge from $x$ to $w$). Then, it is easy to find a node with no incoming edges. Start with any arbitrary node, and then pick any arbitrary node from its incoming CHV, and so on, until we reach a node with an empty incoming CHV. By the proof the earlier in the section, we know that this search will terminate in $O(n)$ time.

Then, we go to each node in this final node's outgoing CHV, and remove the final node from its incoming CHV (this is where we use the constant-time properties of hashmaps/CHVs). This process also takes $O(n)$ time.

Thus, we have a runtime of $O(n)$ for each iteration of the loop in the algorithm to compute a topological order for a DAG.

| cite | improve this answer | |
$\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.