19
votes
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
12
votes
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
12
votes
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
9
votes
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
9
votes
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
9
votes
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
9
votes
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
8
votes
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
7
votes
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
7
votes
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
7
votes
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
6
votes
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
6
votes
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
6
votes
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$ ...
- 693
5
votes
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
4
votes
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
4
votes
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
4
votes
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. Jiménez, A. Marzal, A lazy version of Eppstein’s shortest paths algorithm, in: 2nd International Workshop ...
- 41
4
votes
Accepted
Separating DAGs using separators consisting of lists of nodes and all ancestors
In this answer i assume that $u$ is an ancestor of $v$ if $u$ can reach $v$ by a directed path.
This is basically as hard as Set Cover (Given family $F$ over a universe $U$, find smallest subfamily $F’...
- 3,236
3
votes
Accepted
How to design an algorithm which turns an undirected graph into directed with all nodes of indegree higher than 0?
Edit: modified to emphasize how this approach can be generalized to any arbitrary degree sequence of lower bound in-degrees.
(Apologies if the below is extra verbose -- you said that you're new to ...
- 1,643
3
votes
Breaking cycles in network graph by adding nodes and rerouting edges
This problem is Feedback Vertex Set in disguise, and hence NP-Hard, but I'd imagine there are good heuristics out there (I don't know the references myself, maybe someone can help me out here).
More ...
- 2,333
3
votes
Monotone circuit representations of paths in a graph?
I still do not have any ideas about the general answer to this question, but I think I have an argument against the possibility to construct such a circuit in so-called monotone "decomposable ...
- 7,942
2
votes
Accepted
An edge orientation procedure to generate all acyclic orientations of a graph
The procedure maps each permutation of the vertices to some orientation of the graph whose topological ordering of the vertices is consistent with the permutation.
Every acyclic orientation of the ...
2
votes
Lexicographically minimal topological sort of a labeled DAG
According to this reference (1), the lexicographically first topological order problem is NLOG-complete.
You may want to take a more thorough look at the article to ensure that it covers the case(s) ...
- 3,381
2
votes
Accepted
Obtaining Sets of Ancestors Quickly in a Directed Acyclic Graphs
We can reduce Boolean matrix multiplication to this problem by a three level construction, where the edges from the first level to the second level are determined by the first matrix and the edges ...
- 1,537
2
votes
Accepted
find the most similar topological ordering of a dag
It is NP-hard. The reduction is from $CLIQUE$, so suppose we are given an undirected graph $H$ on $n$ vertices and $m$ edges, with a parameter $k$, and our task is to decide whether $\omega(H)\ge k$. ...
- 13.8k
1
vote
Lighting up all elements of a poset by toggling upsets
Co-worker here. We haven't solved it yet, but here are a few remarks (in case it gives anyone an idea, because we are stuck).
The main thing we have for now is a partial result on so-called crown-...
- 1,217
1
vote
Finding Cheapest n-Path
I am assuming you are given a weighted directed acyclic graph with source $s$ and destination $t$ and you want to find the shortest path from $s$ to $t$ with length exactly $n$ , this can be done ...
- 74
1
vote
Multiple source shortest path with one reversal
You can start by converting your graph $G = (V, E)$ into a new graph $G'$ as follows:
The vertices of $G'$ should be $V \times \{0,1\}$. For every vertex $v \in V$, include the edge from $(v, 0)$ to ...
- 2,748
Only top scored, non community-wiki answers of a minimum length are eligible