Questions tagged [dag]
For questions about the usage and manipulation of Directed Acyclic Graphs (DAG).
166 questions
0
votes
1
answer
47
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 ...
- 113
1
vote
0
answers
52
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....
- 169
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
40
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
66
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
35
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 ...
- 157
1
vote
0
answers
24
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
17
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
79
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$ ...
2
votes
1
answer
149
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 ...
- 29
1
vote
0
answers
67
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
69
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 ...
- 123
1
vote
0
answers
44
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
2
votes
0
answers
133
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
2
votes
1
answer
64
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 ...
1
vote
1
answer
283
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 ...
- 43
0
votes
1
answer
165
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 ...
0
votes
1
answer
57
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 ...
- 2,305
1
vote
1
answer
315
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 ...
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 ...
- 43
2
votes
0
answers
95
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
97
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
115
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
183
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. ...
- 127
0
votes
0
answers
28
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
354
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 ...
- 43
1
vote
0
answers
152
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
1
vote
2
answers
261
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 ...
- 127
0
votes
0
answers
118
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 ...
0
votes
1
answer
461
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 ...
- 9
0
votes
1
answer
407
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 ...
- 45
0
votes
0
answers
115
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$, ...
- 11
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?
- 201
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
88
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.
...
- 915
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 ...
- 25
0
votes
0
answers
61
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
110
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
346
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$ ...
- 11
1
vote
2
answers
319
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 ...
- 11
1
vote
1
answer
201
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 ...
- 115
2
votes
1
answer
375
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 ...
- 195
2
votes
2
answers
3k
views
Can you use Dijkstra's algorithm to find the maximum cost path?
Suppose you have a DAG and the edges are positively weighted, and you want to find the maximum cost path from any node with no in degree to any node with no out degree.
Is it possible to negate all ...
- 121
3
votes
1
answer
1k
views
Maximum number of distinct nodes that can be visited on a single walk
Given a directed graph which may contain cycles, how can I find the maximum number of distinct nodes that can be visited on a single walk?
I have done some research and the most similar-sounding ...
- 133
2
votes
1
answer
495
views
Topological sort and finding longest path in DAG to solve a stacking boxes variation (no rotation)
Given n elements (boxes) I have to output the max number of boxes that can fit one into another. Each box has width (x), height (y) and depth (z). One box j can hold another box k if: ...
user135193
0
votes
0
answers
120
views
Minimum weight $k-$path cover on a DAG proof verification
Suppose you are given a directed acyclic graph $G$ with $n$ vertices and an
integer $k \leq n$. Each edge has an associated weight $w(u,v)$. We want to find $k-$vertex-disjoint paths that cover all ...
- 623
1
vote
1
answer
57
views
Given a list of comparisons, sort items with as few additional comparisons as possible
You have n items x[0], ..., x[n-1]. Beforehand, you're given a list of several comparisons ...
- 542
3
votes
1
answer
197
views
Partition of a $k$-partite graph to minimal number of connected sets
Let $G$ be a $k$-partite directed acyclic graph where the edges are only between two adjacent sets of vertices.
I'm trying to partition the graph to the minimal number of connected sets.
Sets $A_0, ...
- 23