# Tag Info

Accepted

### Counting number of paths between two vertices in a DAG

Here is a dynamic programming algorithm. Given a graph $G = (V, E)$ and two vertices $u, v \in V$. We define the recursive function $C:V\rightarrow \mathbb{N}$, such that $C(w)$ is the number of paths ...
• 4,474
Accepted

### Linear-time algorithm for determining the presence of incomparable pairs in a directed acyclic graph (DAG)

Here is a linear-time algorithm that decides whether a DAG contains at least one incomparable pair of nodes. Do a topological sorting with a linear algorithm. (Yes, topological sorting is very ...
• 39k

### Transitive reduction of rectangle containment hierarchy DAG

Dec. 14, 2018 Standard approach and a heuristic alternative Standard approach -- use graph and distance product We note that transitive reduction is reduceable to transitive closure and vice versa ...
• 372
Accepted

### Is the following figure DAG?

The acronym DAG stands for directed acyclic graph. In other words, a DAG is a (finite) digraph without directed cycles. A digraph is a DAG if and only if it has a topological ordering. In your ...
• 278k
Accepted

### Given an unsorted list of $n$ items, how many random comparisons are needed on average to be able to sort the list?

Asympotically, you'll need $\Theta(n^2 \log n)$ comparisons. Suppose $x_{(1)},\dots,x_{(n)}$ denotes the elements in sorted order. Then if you don't see a comparison between $x_{(1)}$ and $x_{(2)}$, ...
• 162k
Accepted

### Is there a term for these "descendancy" subgraphs of directed acyclic graphs?

Kind of. But we're going to use the usual computer sciency way of describing this, using the language of binary relations. You're probably already familiar with binary relations, like equality $=$, ...
• 22.6k
Accepted

### An algorithm for topological sorting based on depth-first search: why do we need two tags?

Consider the following graph $G = (V, E)$ where $$V = \{1, 2, 3\}, E = \{(1, 3), (2, 3)\}.$$ If your example started at $1$, it will add $3$ to the list and then it will add $1$. In the next step the ...
• 4,474
Accepted

### In a DAG, finding the path with the highest score

Hint: find a topological ordering, and for each vertex $v$, in the topological ordering, compute (the score of) the path with the highest score that ends at $v$.
• 7,545
Accepted

### Why do we use DAG rather than trees to represent search space of a search problem?

A search algorithm is a recursive procedure which accepts an instance and a partial solution and attempts to extend it to a complete solution bit by bit. For example, consider a search algorithm ...
• 278k

### Linear-time algorithm for determining the presence of incomparable pairs in a directed acyclic graph (DAG)

Observe that if there exists a vertex $u$ that is incomparable with another vertex $v$ in a DAG, then $u$'s order in a topological sort can be changed with respect to $v$. Equivalently, $u$'s position ...
• 2,780

### Linear-time algorithm for determining the presence of incomparable pairs in a directed acyclic graph (DAG)

Compute a topological ordering $(v_1, v_2, …, v_n)$ of the DAG. Now consider the recursive following algorithm: if $n = 1$, then there are no incomparable pairs of vertices; if $(v_1, v_2)\notin E$, ...
• 15.9k
Accepted

### Maximum Vertex Set With a Minimum Pairwise Distance Requirement in Directed Acyclic Graphs

[EDIT: updated answer to apply to directed acyclic graphs.] Lemma 1. This problem is equivalent, under approximation-preserving poly-time reductions, to Maximum Independent Set in undirected graphs. ...
• 930
Accepted

### What is the name of a rooted tree whose nodes may have edges to their descendants?

This answer does not have a suggestion as to what existing names we might have. Rather, it is about what names are not appropriate. To be clear, the OP talks about a graph that is a rooted tree with ...
• 39k

### What is the name of a rooted tree whose nodes may have edges to their descendants?

I'm not aware of any standard term. The graphs that you describe are subgraphs of the transitive closure of a tree, if that's of any help to you, but one wouldn't want to use that phrase twenty times ...

### maximum weighted path(s) in a DAG

Your strategy is close, but probably needs some clarification. This is essentially equivalent to finding the longest path in DAGs, which can be done easily in a few ways easiest of which, similar to ...
• 4,511

### Formal definition on graph levels

A DAG (or poset) is ranked or graded if it is possible to assign nodes a rank function $r$ such that if $(x,y)$ is a directed edge, $r(y) = r(x)+1$. We usually choose $r$ so that $\min r = 0$. See for ...
• 278k

### In a DAG, longest path where every vertex has degree at most 2

First, remove all vertices whose degree is greater than 2 (i.e., their degree was greater than 2 in the original graph). The result is a smaller DAG. This can be done in linear time. Now, find the ...
• 162k
Accepted

• 6,202
Accepted

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

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 ...
• 2,780
Accepted

### Shortest paths in $k$-partite DAG

If $|p_k|\leqslant N$ for all $k\in \{1, …, |P|\}$, then a dynamic programming algorithm can compute all those distance in $\mathcal{O}(|V|^2\times N)$ which could be lesser than $|V|^3$. The idea is ...
• 15.9k

### Random directed acyclic graph (Barak-Erdös): find "upstream" vertices

This answer draws heavily from D.W.'s, which got the ball rolling. The algorithm ...
• 73
Accepted

### Topological Sort without modifying the graph or marking edges

Instead of seting a 'mark' flag; node.Marked = true; You can maintain a set of marked nodes in a hashtable or similar; ...
• 168
Accepted

### Flipping all incoming/outgoing edges from a vertex in a DAG

This doesn't hold if we flip both outgoing and incoming edges as shown by @Yuval Filmus. Here is my try of a proof by contradiction for only flipping outgoing of incoming edges (sorry if it's too ...
• 121