# Tag Info

Accepted

### Why is "topological sorting" topological?

The earliest reference I could find for topological sort is from [Lasser61]: A network of directed line segments free of circular elements is assumed. The lines are identified by their terminal ...
• 3,381
Accepted

### Number of simple paths between two vertices in a DAG

Every simple path is uniquely determined by the subset of vertices that it passes through: if you topologically order the DAG (arbitrarily) then a path through any subset of vertices must go through ...
• 50.5k
Accepted

### Lexicographically minimal topological sort of a labeled DAG

With multiple copies of the same label allowed, the problem is NP-hard, via a reduction from cliques in graphs. Given a graph $G$ in which you want to find a $k$-clique, make a DAG with a source ...
• 50.5k
Accepted

### When does a graph admit an orientation in which there is at most one s-t walk?

It's NP-complete by a reduction from not-all-equal-3SAT. To see this, observe that The only valid orientation of a $4$-cycle is one in which the edges alternate orientations. Let $P$ be a three-edge ...
• 50.5k
Accepted

### How expensive may it be to destroy all long s-t paths in a DAG?

[Self answer; this is a shortened version, the old one can be found here] We realized with Georg Schnitger that the answer to my question is strongly negative: there are DAGs (even of constant degree)...
• 6,645
Accepted

### Computing topological sort while keeping edges "short"

Your problem is known under the name MINIMUM DIRECTED BANDWIDTH. It is NP-complete: M.R. Garey, R.L. Graham, D.S. Johnson and D.E. Knuth: "Complexity Results for Bandwidth Minimization" SIAM ...
• 5,742
Accepted

### Minimum cost topological ordering

Your problem is NP-hard. I show this by a reduction from the shuffle problem: given words $w, w_1, \ldots, w_k$ over the alphabet $\{a, b, c\}$, decide whether $w$ can be obtained as an interleaving (...
• 7,942
Accepted

### Isomorphism of ‘ordered’ DAGs / acyclic semiautomata

If you only need to order the outgoing edges the problem is GI complete. Reduce from GI of directed graphs. Given a digraph $D$ make a new one $D’$ as follows: Make a vertex in $D’$ for every vertex ...
• 3,236
Accepted

### Is the isomorphism problem between posets represented by DAGs GI-complete?

Graph isomorphism is GI-complete for DAGs: https://en.wikipedia.org/wiki/Graph_isomorphism_problem#Complexity_class_GI. The problem for partial orders is also GI-complete: We can reduce bipartite ...
• 1,537

### Generalization of Dilworth's theorem for labeled DAGs

With Charles Paperman we have been able to obtain such a result for DAGs labeled with the alphabet $\{a, b\}$. Essentially, we can show that given a DAG $G$ that has large antichains of $a$-labeled ...
• 7,942
Accepted

### Complexity of reachability in directed rooted forests

The problem is L-complete. It’s easier to think about it when the edges are written backwards. That is, I will consider the problem formulated as follows: given a directed acyclic graph such that ...
• 15.3k

### Shortest path in DAG with path dependent arc costs

Without further information on how the costs can vary, the problem is NP-complete. For instance, consider the following rule for setting costs: If an edge would return to a previously-traversed node ...
• 50.5k
Accepted

### Complexity of acyclicity of a "nondeterministic" graph

The strategy I outlined in the comment worked: reading through Bodirsky and Kara's paper, the first solvable case they consider is the case of min-closed languages, and your problem happens to fall ...
• 376
Accepted

### Pagerank in directed *acyclic* graphs (DAG)

As suggested by the comments (thanks!), the answer is positive and rather easy. We want to compute the pagerank of all vertices of a DAG (Directed Acyclic Graph) $G = (V,E)$ with $n$ vertices and $m$ ...

### Survey on Erdős-Pósa?

I don't know about a survey, but I've found a recent PhD thesis, which seems to be well written: Heinlein, Matthias (2019): Erdős-Pósa properties. Open Access Repositorium der Universität Ulm. ...
• 5,504
Accepted

### What is the name of this algorithm on direct acyclic graph?

Looks to me like some additional restrictions on a topological sort: https://en.m.wikipedia.org/wiki/Topological_sorting . Also git already supports this operation for instance git rev-list --topo-...
• 1,508

### Ordering of a DAG minimizing some definition of cost

This problem is NP-complete, as the following reduces to it: https://cstheory.stackexchange.com/a/1936/419 The sketch of the reduction is as follows. From a set of tasks $T$ with $n$ tasks and some ...
• 13.8k

### Finding k shortest Paths with Eppstein's Algorithm

Pseudocode for Eppstein's algorithm (and the authors' lazy version of it) are given in: V.M. Jiménez, A. Marzal, A lazy version of Eppstein’s shortest paths algorithm, in: 2nd International Workshop ...
• 41