Questions tagged [dag]
For questions about the usage and manipulation of Directed Acyclic Graphs (DAG).
166
questions
0
votes
0
answers
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 ...
- 111
1
vote
0
answers
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....
- 171
1
vote
1
answer
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 ...
CommunityBot
- 1
0
votes
0
answers
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 ...
- 111
1
vote
2
answers
39
views
Random directed acyclic graph (Barak-Erdös): find "upstream" vertices
The problem
Consider a set of $N$ vertices $V=\{v_1,v_2,...,v_N\}$. We define a random directed acyclic graph by the set of edges $E$ as follows: for every $i<j$, $e_{ij}:=(v_i\rightarrow v_j) \in ...
- 73
3
votes
0
answers
56
views
Algorithm to find minimum number of cuts in DAG based on a rule
I encountered this problem while doing some “graph”ics programming:
Take a directed acyclic graph where every vertex is given a non-unique label 1..N
You can ‘trim’ the DAG by making a cut that ...
- 31
0
votes
1
answer
31
views
Selecting an Induced Subgraph from a DAG with Specific Conditions
I am working with a Directed Acyclic Graph (DAG), denoted as $G$. The graph has a specific constraint where the out-degree of each vertex in $G$ is at most $2$.
My objective is to select an induced ...
- 859
1
vote
0
answers
21
views
re-rooting a rooted DAG
A "network" is a DAG with a single source (the "root") and all nodes except the root either have in-degree one or out-degree one. A network is "binary" if all nodes have ...
- 111
0
votes
0
answers
16
views
Are there any programs/libraries that can generate all acyclic digraphs on n vertices?
Are there any programs/libraries that can generate all unlabeled acyclic digraphs on n vertices?
I'm thinking of something like Nauty's geng; but for DAGs.
(I have ...
- 121
3
votes
1
answer
73
views
Maximum Vertex Set With a Minimum Pairwise Distance Requirement in Directed Acyclic Graphs
Let $G=(V,E)$ be an unweighted directed acyclic graph with a set $V$ of vertices and a set $E$ of edges. The all-pairs shortest path problem can be solved efficiently using the Floyd-Warshall ...
0
votes
0
answers
8
views
Profitable sequence in a $k$-partite DAG
This question is an extension of this one.
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 $\...
1
vote
1
answer
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$ ...
- 16k
2
votes
1
answer
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 ...
D.W.♦
- 164k
1
vote
0
answers
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 ...
2
votes
1
answer
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 ...
- 6,237
1
vote
0
answers
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 ...
- 133
1
vote
1
answer
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 ...
CommunityBot
- 1
2
votes
1
answer
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 ...
D.W.♦
- 164k
2
votes
0
answers
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 ...
- 121
0
votes
1
answer
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 ...
- 917
0
votes
1
answer
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 ...
- 543
1
vote
1
answer
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 ...
- 16.7k
2
votes
1
answer
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.
- 4,484
4
votes
3
answers
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 ...
D.W.♦
- 164k
2
votes
0
answers
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 ...
- 71
0
votes
1
answer
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 ...
- 9
1
vote
0
answers
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 ...
- 292
1
vote
0
answers
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. ...
- 129
0
votes
0
answers
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 ...
3
votes
1
answer
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 ...
- 2,780
1
vote
2
answers
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 ...
- 16.7k
3
votes
1
answer
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 ...
CommunityBot
- 1
1
vote
0
answers
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 ...
- 11
0
votes
2
answers
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"
...
- 752
1
vote
2
answers
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 ...
D.W.♦
- 164k
0
votes
0
answers
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 ...
D.W.♦
- 164k
2
votes
1
answer
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 ...
CommunityBot
- 1
-1
votes
1
answer
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 ...
CommunityBot
- 1
-1
votes
1
answer
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 ...
- 29.6k
0
votes
1
answer
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 ...
- 16k
0
votes
0
answers
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$, ...
- 39.1k
3
votes
2
answers
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 ...
CommunityBot
- 1
0
votes
1
answer
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?
- 2,872
1
vote
0
answers
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 ...
- 111
3
votes
1
answer
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.
...
- 905
0
votes
1
answer
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 ...
- 29.6k
0
votes
0
answers
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 ...
- 101
0
votes
0
answers
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 ...
- 23
1
vote
0
answers
305
views
Determining whether DAG is semi-connected
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$ ...
- 278k
1
vote
1
answer
198
views
Traversing a directed graph with negative weights
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 ...
- 39.1k