Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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 ...
David Eppstein's user avatar
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 ...
Gamow's user avatar
  • 5,772
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 (...
a3nm's user avatar
  • 9,419
8 votes
Accepted

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. ...
Hermann Gruber's user avatar
8 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 ...
Laakeri's user avatar
  • 1,786
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 ...
daniello's user avatar
  • 3,266
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 ...
a3nm's user avatar
  • 9,419
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 ...
Emil Jeřábek's user avatar
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$ ...
Matthieu Latapy's user avatar
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 ...
zeb's user avatar
  • 376
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 ...
tmn's user avatar
  • 41
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-...
Max New's user avatar
  • 1,695
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 ...
domotorp's user avatar
  • 14k
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’...
daniello's user avatar
  • 3,266
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 ...
a3nm's user avatar
  • 9,419
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 ...
Yonatan N's user avatar
  • 1,642
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 ...
GMB's user avatar
  • 2,403
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$. ...
domotorp's user avatar
  • 14k
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 ...
Laakeri's user avatar
  • 1,786
1 vote

What's the exact complexity of a DFS if we revisit nodes?

Suppose the graph has an adjacency matrix $M$. It's well known that the number of paths of length $k$ from $i$ to $j$ is $(M^k)_{ij}$. Since we care about paths of any length, we are interested in $M^...
Command Master's user avatar
1 vote

random sampling DAGs via nilpotent matrix sampling

For question 2 the first answer is "yes": if $M$ is a $0-1$-nilpotent matrix, then it is the adjacency matrix of some digraph. Now $M^k_{i,j}$ is well-known to be the number of paths of ...
thibo's user avatar
  • 193
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-...
M.Monet's user avatar
  • 1,429
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 ...
Rajat De's user avatar
1 vote

Efficient algorithm for generating data dependency DAG from lists of memory ranges and access modes

Build an interval tree storing all of the ranges that have been written. That data structure lets you efficiently determine, for any given memory address, the time when it was most recently written. ...
D.W.'s user avatar
  • 12.1k
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 ...
Mikhail Rudoy's user avatar
1 vote

Why is "topological sorting" topological?

Topology is the study of how "shapes" change when you apply continuous transformations to them. The central object of study is a topological space, which can be thought of as a way of saying ...
user513093's user avatar

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