Questions tagged [dag]
For questions about the usage and manipulation of Directed Acyclic Graphs (DAG).
146
questions
1
vote
1
answer
31
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
969
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
84
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
54
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
87
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 ...
- 280
1
vote
0
answers
94
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
26
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
186
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 ...
- 33
1
vote
0
answers
124
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
125
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 ...
- 125
0
votes
0
answers
96
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 ...
-1
votes
1
answer
189
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
154
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
64
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
38
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
56
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.
...
- 847
0
votes
1
answer
1k
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
52
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
87
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
190
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
164
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
154
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
244
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 ...
- 191
2
votes
2
answers
2k
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
708
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
303
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
98
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 ...
- 594
1
vote
1
answer
55
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 ...
- 512
3
votes
1
answer
161
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
3
votes
0
answers
33
views
Online cycle detection but not quite: the Featherstitch problem
Featherstitch (Frost et al., 2007) is an approach for representing data consistency requirements for disk storage. This question concerns a graph-theoretic problem (§4.1 in the paper) that its ...
- 131
1
vote
0
answers
83
views
minimising Longest-Path in DAG
Assume we have weighted DAG (directed-acycle-graph), source s and target t.
Define the number of edges as $E$.
Given $0<\alpha<1$:
Choose $\alpha*E$ edges to cut their weight by half so that the ...
- 11
0
votes
0
answers
49
views
identify nodes with paths of unique length from source
Let us consider a Directed Acyclic Graph $G(V,E)$ such that all edges have unit weight. Let $s$ be a source node, $s\in V$ and a set of destination nodes, $D\in V\backslash s$. My problem is to find a ...
0
votes
1
answer
200
views
DAG for contiguous subsequence of maximum sum
I have trouble understanding DAG behind the "contiguous subsequence of maximum sum problem". Let's say I denote by S(i) maximum of sums of contiguous ...
- 113
1
vote
0
answers
32
views
How to compute all inequivalent (under Aut(P)) nonnegative integer weight assignments (with fixed sum) to the vertices of a finite poset P?
Let $P$ be a poset on $n$ points, $\text{Aut}(P)$ its automorphism group, and $a_1,a_2,\dots,a_k$ the lengths of the orbits under $\text{Aut}(P)$.
Goal: An algorithm to generate a member from each ...
- 123
2
votes
2
answers
287
views
DAG: When adding an edge that would normally result in a cycle, is there an algorithm to split the graph instead?
Summary
I am using a DAG to compress a tree structure with many repeated nodes (the repeated nodes only very seldomly do not also have repeated edges out.)
Normally, when attempting to add an edge to ...
- 133
1
vote
0
answers
66
views
What does a recursive min s,t-cut optimize?
Consider the following algorithm sketch:
Given an edge-weighted directed acyclic graph $G = (V, E, w : E \to \mathbb{N})$, adjoin a temporary source $s$ and sink $t$ to get $G' = (V', E', w')$. $G'$ ...
- 364
1
vote
0
answers
20
views
In a DAG, what is the name of the process replacing no branch path with a single vertex
In my work, I meet a process for DAG, and need to explain it in my report. So, I would like to know the name of the process.
The process is very simple. The vertices of degree two except roots and ...
- 239
1
vote
2
answers
215
views
Find every edge for which every s,t-path in a DAG goes through that edge
Given a connected sourced/sinked directed acylic graph $G = (V, E \subseteq V^2, s \in V, t \in V)$, we want to enumerate the edges $e \in \mathsf{Bottleneck}(G) \subseteq E$ for which every $s$,$t$-...
- 364
2
votes
2
answers
117
views
Path graph partitioning, minimizing cut while minimizing maximum total node weight in each part
Suppose there is a path (linear) graph $G = (V, E)$ where $V = \{0, \ldots, n - 1\}$ and $E=\{(0, 1), (1, 2), \ldots, (n - 2, n - 1)\}$, with edge weights $w_e : E \to \mathbb{N}$ and vertex weights $...
- 364
1
vote
0
answers
90
views
Is there a data structure to represent changes to a DAG over time, with fast reproduction of instances of the DAG?
Consider a directed acyclic graph (DAG) of topics and links. Apart from the root topic, topics are situated under one or more parent topics, and links, as well, are situated under one or more parent ...
- 111
2
votes
1
answer
182
views
edge coloring a directed acyclic graph
I have an edge coloring problem as follows:
Suppose we have a DAG which has a source vertex s and an end vertex e, in addition, all the paths from s to e are of the same length say L. We define L ...
- 21
3
votes
1
answer
92
views
Why do we use DAG rather than trees to represent search space of a search problem?
I saw people use DAGs to represent the search space of a search problems like the travelling salesman problem. Why is this better than the tree representation? Is the reason to save memory space on ...
- 167
0
votes
1
answer
165
views
Alternatives for finding sources in a DAG
I have a hard time seeing what the alternative approach is in linearizing a directed acyclic graph (DAG). Chapter 3 of Algorithms by Dasgupta et al. states:
Property Every dag has at least one source ...
- 659
0
votes
1
answer
541
views
Vertices reachable from negative-weight cycles in Bellman-Ford
TLDR: I want to know if there's a simple way to fill in distances for all vertices reachable from negative weight cycles (not just ones on the cycle itself) once Bellman-Ford has found a negative-...
- 838
3
votes
2
answers
195
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 ...
- 31
3
votes
0
answers
103
views
Using vector clocks vs. directed acyclic graph for causality detection in distributed systems
I'm trying to understand how vector clocks compare to DAGs for causality detection in a distributed system.
When trying to detect causality relations in a distributed system, a very commonly proposed ...
- 131
0
votes
0
answers
49
views
Given start strings, find simplest DAG that constructs target strings by concatenation
Say we have a number of start strings (green) and a number of target strings (red). Two strings can always be concatenated to a new string which can then be arbitrarily often reused (two arrows in, (1,...
- 191
1
vote
1
answer
500
views
If there is no Hamiltonian path in a DAG then there are at least two different Topological sorts
I understand the concept that if there is no Hamiltonian path so there will be 2 smaller paths and with them I can build more then one topological sort but I am not sure how make it formal.
Can you ...
0
votes
0
answers
127
views
Transitive reductions of transitive closure
Is there a name for the relationship between two DAGs A,B where B is one of the transitive reductions of the transitive closure <...
- 177