Hot answers tagged

9 votes
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 ...
Narek Bojikian's user avatar
6 votes
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 ...
John L.'s user avatar
  • 38.8k
5 votes

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 ...
bzliu94's user avatar
  • 372
5 votes
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 ...
Yuval Filmus's user avatar
5 votes
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)}$, ...
D.W.'s user avatar
  • 158k
5 votes
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 $=$, ...
Pseudonym's user avatar
  • 22k
4 votes
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 ...
Narek Bojikian's user avatar
4 votes
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$.
xskxzr's user avatar
  • 7,425
4 votes
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 ...
Yuval Filmus's user avatar
4 votes

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 ...
Russel's user avatar
  • 2,735
4 votes

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$, ...
Nathaniel's user avatar
  • 13.8k
3 votes
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 ...
John L.'s user avatar
  • 38.8k
3 votes

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 ...
David Richerby's user avatar
3 votes

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 ...
ryan's user avatar
  • 4,451
3 votes

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 ...
Yuval Filmus's user avatar
3 votes

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 ...
D.W.'s user avatar
  • 158k
3 votes
Accepted

Efficient algorithms for identifying the diamond fork&join vertices and the diamond pairs in directed acyclic graph?

$G=(V,E)$ is the graph we work on. Problem 2: $\Diamond_F(reverse(G))=\Diamond_J(G)$, where $reverse(G)$ reverses all the edges of G. Problem 3: This can be solved in $O(nm)$ time. For each vertex $...
Chao Xu's user avatar
  • 3,053
3 votes
Accepted

Number of states in an AND-OR DAG

Your problem is equivalent to counting the number of satisfying assignments for a monotone Boolean circuit. The restricted version in which the circuit is of the form $(x_{i_1} \lor x_{j_1}) \land \...
Yuval Filmus's user avatar
3 votes
Accepted

Algorithm for finding an irreducible kernel of a DAG in O(V*e) time, where e is number of edges in output

I do not know about their algorithm, but the problem is easy to solve in $\mathcal{O}(V \cdot e)$ time. The idea is to just do a DFS from every node to find vertices that can reach it. Normally this ...
Antti Röyskö's user avatar
3 votes
Accepted

Why do we do topological sorting to find shortest or longest path in weighted DAG?

By using this algorithm the expected time complexity would not be O(V+E) as we have to visit an edge multiple times. ...
vivek gupta's user avatar
3 votes

Find every edge for which every s,t-path in a DAG goes through that edge

Compute the dominator tree of the flow graph $(G,s)$, i.e., the graph $G$ with source node $s$. Let $s=v_0,v_1,\dots,v_{k-1},v_k=t$ be the sequence of nodes in the path from $s$ to $t$ in the ...
D.W.'s user avatar
  • 158k
3 votes
Accepted

Maximum number of distinct nodes that can be visited on a single walk

The problem you have is the following: You have a directed graph and you are allowed to visit the same vertices and edges many times over. You want to find a walk starting in a vertex $s$ that ...
Pål GD's user avatar
  • 15.8k
3 votes

Can you use Dijkstra's algorithm to find the maximum cost path?

No, Dijkstra's algorithm will not work. Consider the following counter-example: $V = \{s,u,t\}$ and $E = \{(s,u),(u,t)(s,t)\}$. The weights on the edges is as follows: $w(s,u) = 1$, $w(u,t) = 3$, and $...
Inuyasha Yagami's user avatar
3 votes
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 ...
Russel's user avatar
  • 2,735
2 votes
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; ...
Steve Cooper's user avatar
2 votes
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 ...
ghord's user avatar
  • 121
2 votes
Accepted

Construct a DAG using Tarjan

Construct a new graph whose vertex set is the strongly connected components. Now go over all edge in the original graph, and if they connect two different strongly connected components, add the ...
Yuval Filmus's user avatar
2 votes

Formal definition on graph levels

This is sometimes known as a level structure, and they come up in e.g., certain algorithmic applications.
Juho's user avatar
  • 22.5k
2 votes

Longest path in DAG or finding DAG diameter

But which method could help us to find the maximum path between all two vertices and pick the maximum one as graph Diam. That's not how the diameter is usually defined; it's rather the maximum ...
Raphael's user avatar
  • 72.3k

Only top scored, non community-wiki answers of a minimum length are eligible