Skip to main content
10 votes
Accepted

What don't I understand in topological sort using DFS?

Main misunderstanding is when nodes are added to the answer - you add them when you leave them, right before/at backtracking So you check A, check C, find that C is terminal - so you add C at the end ...
Noone AtAll's user avatar
7 votes

Genetic algorithms applied to topological orderings of a DAG

There is no one correct answer. You may have to try different possibilities and see how well they work. One candidate mutation operation is the following: pick a random pair of adjacent nodes (i.e., ...
D.W.'s user avatar
  • 161k
6 votes

Find minimum of a function only knowing the ordering of a set of input points

You can't. The function could be anything. For example, consider $$f(x) = \begin{cases} g(x) &\text{if }x \ne \alpha\\ -10^{100} &\text{if } x = \alpha \end{cases}$$ where $\alpha \in \...
D.W.'s user avatar
  • 161k
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
  • 39k
6 votes
Accepted

Is there an algorithm to minimize working set during a topological traversal?

Deciding if a topological ordering with working set of size $\le k$ exists is NP-complete, even in bipartite graphs. We can reduce pathwidth computation to this problem. Let $G$ be a undirected graph,...
Laakeri's user avatar
  • 1,339
6 votes

Topological sort with minimum maximal distance in array

The measure you are trying to minimize is called (directed) bandwidth. Finding a minimum directed bandwidth ordering is NP-hard.
Steven's user avatar
  • 29.5k
5 votes
Accepted

What is the relation between Topological Sort and Strongly Connected Components?

One connection could be the following: Given a graph $G$, construct the graph $G'$ in which every connected component of $G$ is a node, and two nodes in $G'$ have a (directed) edge if there is an edge ...
nir shahar's user avatar
  • 11.6k
4 votes

How to edge-color a directed acyclic graph so that every path visits none or all edges of each color?

I present a refinement on HEKTO's algorithm that I think works and should be more efficient: it runs in $O^*(\min(n^3,m^2))$ time. Theory Let $P(a)$ denote the set of paths that start at $s$, go ...
D.W.'s user avatar
  • 161k
4 votes
Accepted

How to edge-color a directed acyclic graph so that every path visits none or all edges of each color?

You can color a pair of arcs $(a_1,a_2)$ by the same color, if and only if all the paths from the source to the sink, passing through the arc $a_1$, also pass through the arc $a_2$. Let's consider the ...
HEKTO's user avatar
  • 3,098
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
  • 15.8k
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,780
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,780
3 votes

How to edge-color a directed acyclic graph so that every path visits none or all edges of each color?

It sounds to me like the greedy algorithm should work, I'm not able to come up with any counter-examples, however, I haven't had time to try to prove the claim either. Terminology Definition. Let $s$...
Pål GD's user avatar
  • 16.7k
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

How to edge-color a directed acyclic graph so that every path visits none or all edges of each color?

There is a simple randomized linear-time algorithm (one-sided error). It is based on HEKTO's idea, using the equivalent relation. The algorithm chooses weight $w_a$ for each arc $a$. Then, the ...
pcpthm's user avatar
  • 2,662
2 votes

How to edge-color a directed acyclic graph so that every path visits none or all edges of each color?

This answer is an improvement for my (already accepted) original answer, which describes an exact, but potentially very slow algorithm. This improvement was inspired by the @pcpthm answer, however I ...
HEKTO's user avatar
  • 3,098
2 votes

Determine whether there exists a path in a directed acyclic graph that reaches all nodes without revisiting a node

Assume the graph is a directed acyclic graph throughout. The algorithm is correct In the first recursion, the algorithm finds a node $u$ that has no incoming edges. In the second recursion, the ...
John L.'s user avatar
  • 39k
2 votes
Accepted

Genetic algorithms applied to topological orderings of a DAG

Another way of performing the combination operation is this: Randomly interleave both linear orderings (obtaining a tuple containing each node twice) Discard the second occurrence of each node The ...
Klaus Draeger's user avatar
2 votes

Genetic algorithms applied to topological orderings of a DAG

I am not sure if this will be good enough for the performance of your problem, but here are some things I could think of. Combination Find the shortest prefix of the two topological sequences which ...
Raziman T V's user avatar
2 votes

Find minimum of a function only knowing the ordering of a set of input points

The answer by @D.W. is correct that any search space will need some structure in order to make progress. However, I think it would be pessimistic to conclude that the No Free Lunch theorems apply; ...
Warbo's user avatar
  • 632
2 votes
Accepted

Checking if there exists a 'source' vertex

Hint: if you find all the strongly connected components in the graph, the quotient graph of the SCCs is a DAG. In this DAG, if there is a meta-node that can reach all the other meta-nodes, you have ...
Pål GD's user avatar
  • 16.7k
1 vote

Algorithm to identify common subsets

I suggest creating a DAG, as you suggest, with one vertex per set, and an edge from set $S$ to set $T$ if $T$ is guaranteed to be a subset of $S$ (i.e., the filters of $T$ are a superset of the ...
D.W.'s user avatar
  • 161k
1 vote

Is there any Algorithm to check a vertex\node's partial order in terms of other vertices\nodes for a given graph?

I am assuming that you're graph $G$ is a DAG. Let $v$ be your reference vertex. Perform a DFS starting at $v$ to find all vertices reachable from $v$. These vertices must have a lower order from $v$. ...
Russel's user avatar
  • 2,780
1 vote

Why compute finish time in topological sort

Denote $\text{post}(v)$ (for postvisit number) its finish time. Then for any directed graph $G = (V, E)$, the two following properties are equivalent: $G$ contains a cycle; there exists an edge $(u, ...
Nathaniel's user avatar
  • 15.8k
1 vote

Why compute finish time in topological sort

I guess the algorithm you presented is from CLRS. You are right that the finishing time is not necessary for the algorithm to work. Once the vertex is completely explored (all its neighbors are ...
Russel's user avatar
  • 2,780
1 vote
Accepted

Topological sort and finding longest path in DAG to solve a stacking boxes variation (no rotation)

The topological order is not guaranteed to be a solution. Indeed the topological order clearly has length $n$ while there are instances in which it is not possible to stack all boxes. As an example ...
Steven's user avatar
  • 29.5k
1 vote
Accepted

DFS produces the correct Topologically ordered sequence

Before I get to the proof, let me just clarify that the algorithm using DFS would be to process edges in decreasing order of finishing times while running DFS on the input graph. Now to prove that the ...
devam_04's user avatar
  • 285
1 vote
Accepted

Valid orderings for topological sort

A source is a vertex with in-degree zero. An order of the vertices is a topological order if deleting the vertices in that order deletes only sources. Hence, you can verify that an order is ...
Pål GD's user avatar
  • 16.7k
1 vote

Valid orderings for topological sort

You can answer your own question by checking whether, for each edge $(u,v)$ of the graph, $u$ appears before $v$ in each of the three candidate topological orders that you listed.
Steven's user avatar
  • 29.5k
1 vote

Ordering of operations in a DAG of git commits

Assuming I understand the semantics: You cannot concurrently Create the same bug report twice, so that's not a problem Title could be a Last-Writer-Wins (LWW) register. If two users perform SetTitle ...
Marc's user avatar
  • 11

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