# Questions tagged [dag]

For questions about the usage and manipulation of Directed Acyclic Graphs (DAG).

166 questions
Filter by
Sorted by
Tagged with
13 views

### Subgraphs of DAG minimizing overlap

Given a DAG, it has a number of 'source' nodes - nodes whose in-degree is zero. Each source node has a set of nodes reachable from it. I would like to partition the source nodes into $k$ disjoint ...
1 vote
49 views

### Version of SSSP

Let $G=(V,E)$ a directed graph s.t $|V|=n$. Let $w:E \to \mathbb{R}$ a weight function. Describe an algorithm which finds the minimal-weighted walk of length $\leq n$ from $s \in V$ to all other nodes....
1 vote
197 views

### Generating project network graph

I had a problem of generating project network graph (like there and there) from list of activities and their dependencies. Informal description: Every activity is represented as edge of directed ...
32 views

### What is this graph?

I am seeking nomenclature to describe the family of graphs detailed below, and literature about its processing, traversal, costs, etc. Any and all input is welcome, e.g. papers, textbooks, helpful ...
1 vote
39 views

1 vote
44 views

### Shortest paths in $k$-partite DAG

Let $D(V, A)$ be a $k$-partite DAG; $P = \{ p_k : 1 \leqslant k \leqslant |P| \}$ such that $p_k \cap p_l = \emptyset$, $\forall k,l : k \neq l$, and $\bigcup_{1 \leqslant k \leqslant |P|} p_k = V$ ...
110 views

### Dynamic Programming as DAGs - Solution Always Shortest Path?

I've been trying to get a deeper understanding of how dynamic programming works and came across how it can be represented as directed acyclic graphs (DAGs). It's easy to see why, nodes represent the ...
1 vote
65 views

### Total combinations in DAG with upper bound on node value

There is a directed acyclic graph with M edges. There is only one component (If they were undirected edges all nodes will be reachable will from one to another). An edge from a to b means value of ...
61 views

### Does the Nth iteration of Bellman-Ford relax every edge reachable from a negative cycle?

Consider a graph $G$ with $N$ nodes, with the distance of each node initially set to infinity (there is no start node). If there are no negative cycles in the graph, then after $N - 1$ iterations of ...
1 vote
42 views

### Bucheim-Walker corollary for DCGs

The Bucheim-Walker algorithm is used for drawing trees. However, there are many real-world examples where Directed Cyclic Graphs would benefit from such an algorithm (e.g. family trees with ...
1 vote
200 views

### How to find the learned clause from a UIP cut

I would guess that this question is going to make some people wonder how I haven't already found a solution looking through papers -- but I do not see a clear algorithm. In implementing CDCL, I read ...
63 views

### Non-dominated maximal paths in a DAG

Let $D(V, A)$ be a DAG. We call a dominated path in $D$ a path $P$ such that $P$ is maximal and $\exists P^{'} \in D . (P^{'} \text{ is maximal } \wedge V(P) \subset V(P^{'}))$ that is, $P$ is a ...
128 views

### Finding highest value/weight ratio in dependency graph: NP-hard?

I have the following problem, and would like to figure out whether or not it's NP-hard - primarily to know that searching for a polynomial algorithm for it is futile. Approximations are possible, and ...
159 views

### Why not n^2 comparisons in the Alien Dictionary problem on leetcode?

Here's the problem statement (as given on GeeksForGeeks website): Given a sorted dictionary of an alien language having N words and k starting alphabets of standard dictionary, find the order of ...
50 views

### Can a trie or DAWG loop?

I am looking at DAWGs, which are compressed tries, like this: It is an acyclic graph though, and I'm wondering if you are allowed to create loops or cycles in such a data structure. For example, I am ...
1 vote
260 views

### Minimum edges removed to turn a strongly connected graph into an acyclic graph

If I start with a directed graph that is strongly connected, is there a straightforward way / algorithm to find the smallest set of edges to remove, such that the result is a directed but acyclic ...
3k views

### Counting number of paths between two vertices in a DAG

I need an algorithm that computes the number of paths between two nodes in a DAG (Directed acyclic graph) I need a dynamic porgramming solution if possible.
1k views

### Linear-time algorithm for determining the presence of incomparable pairs in a directed acyclic graph (DAG)

I am seeking a linear-time algorithm to determine whether a directed acyclic graph (DAG) contains at least one pair of incomparable nodes. Two nodes $u$, $v$ are said to be incomparable if there is ...
91 views

### Finding a maximum induced DAG in a digraph

I have a digraph D on n vertices formed in the following manner: I start with k ordered (not sorted) lists of integers, with each integer from 1-n in at least one list. Integers do not show up more ...
88 views

### Correct Term for describing "diamond" subgraphs in a Directed Acyclic Graph

I am trying to research handling a specific type of possible subgraph in directed acyclic graphs. However, I am struggling to find the correct term to use. If we consider the subgraph S to be in a DAG ...
1 vote
109 views

### Topological sort of DAG that minimizes maximum number of unique-source-edges crossing through any node when placed in 1-d line

Consider a DAG such as one shown below: How do I find a particular topological order of nodes, such that when the nodes are placed in a straight line, the maximum number of unique-edges that cross ...
1 vote
172 views

### Reverse one edge to make the most expansive strongly connected component

Problem statement We're given a directed simple acyclic graph with weighted vertices. Find an edge $e$ such that reversing it would create a strongly connected component (SCC) whose price is maximal. ...
27 views

### Tree Width of Directed Graph

I'm Nestor Mermoz Thea. I have two definition over the Directed strong pseudoforest and Directed weak pseudoforest that I don't really well understand. Directed weak pseudoforest: A directed weak ...
317 views

### Getting all vertices with fixed index in their topological ordering of a DAG

During my self study for graphs, I'm currently learning about topological sorting and ran into a question I'm not sure how to solve. There are typically more than one order of a topological ordering ...
1 vote
307 views

### Maximum flow in integer flow network

Let's say you have a maximum integer flow function in a network with 7 directed edges, meaning the flow cannot be increased anymore. The capacity of each edge is then increased by one. The capacity of ...
126 views

### How to generate, validate, and invalidate a set/list of numbers in O(1) time and space?

Imagine my server is generating "tokens" of some sort for a client on a regular basis. When a client asks for a token, the server responds with a new value (and any other supplemental ...
1 vote
144 views

### Directed Acyclic Graph with minimized merging nodes

Suppose that we have a set of paths that all of them strat from the source "I" and end to the destination "O". The paths might have shared nodes. We are allowed to change the ...
1k views

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

I was wondering why do we need to do the topological sort before performing relaxing of edges. Wouldn't it'd be better if we do : if starting vertex is "s" ...
1 vote
215 views

### reverse single edge in DAG and keep it a DAG

If I reverse a single edge in a DAG, how can I efficiently propagate the effects of that (e.g. change other edges) such that I don't introduce any cycles by said reversal? Is there a named algorithm ...
116 views

### Using topological sort to find inconsistencies represented by cycles in directed graphs

Consider the following scenario. Let $x_1,...,x_n$ be a group of cars that all drive from some point A to some point B. Each car starts driving in index order. i.e. $x_1$ starts driving strictly ...
361 views

### House Robber DP Algorithm (Not three in a row)

This is a similar question to A variant of the house robber problem but instead of the general case, I'm wondering how you would solve the standard house robber problem, but when you cannot rob from ...
52 views

### Generating topological sequence from DAG with additional "not appearing before" constraints

DAG specifies the relationship of one node must appear after another. What if I add an additional constraint where one node cannot appear before another on top of the DAG? Is there an algorithm for ...
407 views

### Converting a Directed Acyclic Graph to a Directed Tree

I'm wondering if anyone can help me with this. Say I have a DAG, I understand that it has no directed cycles, but it can have loops ( "diamonds" ). My question is, is there a known way to ...
347 views

### Transitive Closure of a graph

Assuming we have a DAG, $G = (V, E)$, and we know that we can calculate $G$'s transitive closure in time complexity of $f(|V|, |E|)$, whereas $f$ is monotonic increasing function. Show that given a ...
108 views

### DAG graph where indegree >= outdegree and indegree = 0 => outdegree <= 1, cover all vertex with min amount of paths

Given a graph $G = (V, E)$ where G is directed: $\forall \ e \in E$ : $e$ has a direction. G is acyclic (no cycles): $\forall$ path $v_1, \dots , v_n : (v_n, v_1) \not\in E$. If indegree $\gt0$, ...
225 views

### Ordering of operations in a DAG of git commits

Context: I'm looking for a better state resolution algorithm for https://github.com/MichaelMure/git-bug Summary of the current algorithm and shortcomings git-bug is a distributed bug-tracker that ...
40 views

### Name of this graph family?

Suppose I start with a directed chain graph of length $n$: And then I add $k$ edges, with a restriction that the result is a planar DAG: Is there a name for this graph family?
1 vote
17 views

### Aggregating pairwise ratings in a graph

A finite set of individuals provide bounded non-binary pairwise ratings of other individuals (say, -10 to +10), forming a directed graph (cycles possible). I'd like to determine aggregate ratings for ...
85 views

### When inserting a new vertex in a DAG, what possible changes are there to the edges

Background: I'm trying to program a generic method to add a node to a Directed Acyclic Graph. This method should allow the caller to specify the possible effects on the graph, specifically the edges. ...
2k views

### modify dfs to find longest path

Let $G = (V, E)$ be a directed acyclic graph. Let every node $v \in V$ have an additional field $v_d$. For each vertex $v \in V$, we need to store in $v_d$ the length of the longest path in $G$ that ...
58 views

### Minimise vertex loss converting DCG to DAG

I have a DCG that I want to lay out with the parents on the left and children to the right. I want to maximise the number of all children present to the right of all parents whilst minimising the ...
106 views

### Dijkstra algorithm for DAG

Assuming we have a K-Partite DAG (edges are directed from one level to the next) with edge weights either 0, 1 or 2. We are looking for the shortest path between a node from group 0 to group k-1 (path ...
1 vote
I have been asked to write an algorithm which determine whether a DAG is semi-connected. (Recall that a DAG is semi-connected if for any pair of vertices $x,y$, there is either a path from $x$ to $y$ ...
Let $G = (V, E)$ be a directed graph with negative edge weights and no cycles, and $L:V \to \mathbb [0, \infty[$ be a function defined over this graph. This graph represents all possible paths a ...