Questions tagged [dag]
For questions about the usage and manipulation of Directed Acyclic Graphs (DAG).
146
questions
16
votes
4
answers
12k
views
Transitive reduction of DAG
I am looking for O(V+E) algorithm for finding the transitive reduction given a DAG.
That is remove as many edges as possible so that if you could reach v from u, for arbitrary v and u, you can still ...
- 291
9
votes
1
answer
472
views
Shortest Path in a Directed Acyclic Graph with two types of costs
I am given a directed acyclic graph $G = (V,E)$, which can be assumed to be topologically ordered (if needed). Each edge $e$ in G has two types of costs - a nominal cost $w(e)$ and a spiked cost $p(e)$...
- 141
7
votes
1
answer
544
views
Transitive reduction of rectangle containment hierarchy DAG
I am looking for a $O(|V| + |E|)$ algorithm for finding transitive reduction of a rectangle containment hierarchy DAG, i.e. a directed edge exists from one rectangle to another if the first rectangle ...
- 372
6
votes
1
answer
5k
views
Finding all paths between a set of vertices in a DAG
Given a graph G= (V, E) that is:
directed,
acyclic,
non-weighted,
may have more than one edge between two vertices (thus, source and destination are not enough ...
- 413
6
votes
1
answer
712
views
Efficient algorithms for identifying the diamond fork&join vertices and the diamond pairs in directed acyclic graph?
Given a DAG (directed acyclic graph) $G=(V,E)$ without multiple edges, i.e., edges with the same source and target vertices, we define:
A vertex $v_j \in V$ is a diamond-join ($\Diamond_J$) vertex if ...
- 9,471
5
votes
1
answer
280
views
Algorithm for finding an irreducible kernel of a DAG in O(V*e) time, where e is number of edges in output
An irreducible kernel is the term used in Handbook of Theoretical Computer Science (HTCS), Volume A "Algorithms and Complexity" in the chapter on graph algorithms. Given a directed graph $G=(V,E)$, ...
- 218
5
votes
1
answer
1k
views
Approximating the biggest acyclic subgraph of a given weighted digraph $G= (V,E)$
The base scenario is this: We're given a weighted, directed graph $G= (V,E)$, and are tasked to find an approximating algorithm which returns a digraph $G' = (V,E')$ (i.e. which only deletes edges) so ...
- 659
5
votes
0
answers
420
views
Minimum Number of Edges Added to a DAG to get Unique Topological Order
The question is simple:
Given an unweighted directed acyclic graph, $G = (V, E)$, what is the minimum number of directed edges we need to add to $E$ such that the resulting graph $G = (V, E')$ has ...
- 4,421
5
votes
0
answers
136
views
Has this graph-theoretic problem got a known name? Is it NP-hard?
I am considering the following problem.
We are given a Directed Acyclic Graph. In general, there would be some number of subgraphs that, contracted into one node, would make it a tree. For example, ...
- 448
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
4
votes
1
answer
165
views
Is there a term for these "descendancy" subgraphs of directed acyclic graphs?
Consider a directed acyclic graph $G$ with vertex set $V$. Choose a vertex $v$, and let $H$ be the subgraph containing $v$ and all other vertices in $G$ that are reachable from $v$ (along with the ...
4
votes
2
answers
12k
views
maximum weighted path(s) in a DAG
Given a weighted directed acyclic graph (DAG), I need to find all maximum weighted paths between the start node(s), i.e. zero incoming edges, and the end node(s), i.e. zero outgoing edges. My current ...
- 141
4
votes
1
answer
3k
views
Strongly connected components on a DAG
What is supposed to be the right result of an SCC algorithm running on a DAG.
should it return "no components" or "there are V components of size 1"?
I suspect it will return the latter (since it ...
- 431
4
votes
0
answers
97
views
Can the running time be reduced to something lower than $O(d^4)$?
Imagine I have a weighted complete directed graph $G$ with $d$ vertices(so $d(d-1)$ edges) and I want to do the following:
Set $D$ to be a DAG with the same set of vertices but without any edges
sort ...
- 71
4
votes
0
answers
4k
views
Fastest algorithm for shortest path with atmost k edges on a DAG with non-negative edge weights?
(Please note, this is not a duplicate to Shortest path with exactly $k$ edges OR Shortest path with a fixed number of edges. What I want is a better algorithm)
The problem under consideration is to ...
3
votes
1
answer
129
views
Given an unsorted list of $n$ items, how many random comparisons are needed on average to be able to sort the list?
There is an unsorted list of $n$ items $x_1, \ldots, x_n$. Until you can sort the list, you are given one of the ${n \choose 2}$ possible binary comparisons uniformly at random (with replacement).
On ...
- 512
3
votes
2
answers
876
views
Formal definition on graph levels
I'm looking for a formal definition of "graph levels" on a DAG. This example should illustrate what I mean by this.
The node 0 has no edges directed towards it, therefore this has level 0. Next is ...
- 31
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
3
votes
2
answers
735
views
Fewest traversals to visit all vertices of DAG
I want to find the fewest traversals to visit all vertices of a DAG. To take a very simple case:
...
- 143
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
3
votes
1
answer
710
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
3
votes
2
answers
1k
views
How to find all topological sortings of a special DAG in O(N^2)
I came across the following question in a hackerrank competition, which is based on topological sorting of a DAG.
https://www.hackerrank.com/contests/hourrank-29/challenges/birthday-assignment/forum
...
- 141
3
votes
1
answer
204
views
Number of states in an AND-OR DAG
Consider a DAG of $N$ nodes, where each node can take on one of two value, either false, $0$ or true, $1$. Additionally, let each non-leaf nodes (nodes with parents) be assigned a type: either an AND ...
- 371
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
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
1
answer
434
views
Construct a DAG using Tarjan
This is a question related to a homework assignment so I guess I'm asking for hints, if that's ok? Basically, I'm wondering if there is some way to use Tarjan to compress the nodes in every SCC found ...
- 33
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
1
answer
129
views
How to detect "tree-able" set-families?
A set-family (a set of sets of elements) is called tree-able if the elements can be arranged on a directed tree such that each element appears in exactly one node, and each set in the family ...
- 5,790
3
votes
1
answer
122
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 ...
- 131
3
votes
1
answer
46
views
Transitive reduction with vertex additions?
The transitive reduction of a (finite) directed graph is a graph with the same vertex set and reachability relation and a minimum number of edges. However, what if vertex additions are allowed? In ...
- 404
3
votes
1
answer
418
views
Construct a DAG from given multiple topological orderings
I need to construct a DAG, from its given topological orderings (i.e. the graph $G$ created must have all the orderings given as its topological orderings). For simplicity, the vertices are labeled as ...
- 115
3
votes
1
answer
1k
views
Merging nodes of a DAG
I would like to merge connected nodes with a specific attribute of a directed acyclic graph. The purpose is to detect max connected clusters of blue nodes and merge them.
After each merge operation, ...
- 153
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
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
3
votes
0
answers
114
views
Order the vertices to maximize the weights of edges in the induced subgraph
I have a complete directed graph $G:=(V,E)$ with directed edge weights $c_{ij}$ for every distinct nodes $i$ and $j$.
Goal: Find the topological order such that the smallest edge weight of the ...
- 71
3
votes
0
answers
183
views
Assign weights to the edges in a DAG so that, for all S and T, all paths from S to T have equal weight
I have a DAG, and on each edge, I have a minimum and maximum weight. I would like to assign (or determine it's impossible to assign) exact weights to each edge so that
Each edge's weight is between ...
- 151
3
votes
0
answers
511
views
Transform a DAG to fork-join format
I have a directed acyclic graph where the nodes are tasks and the edges are dependency relations between tasks - the edges go from the dependency to the task that depends on it.
It is possible that ...
- 31
3
votes
0
answers
1k
views
Lowest single common ancestor in a Directed Acyclic Graph?
I was reading how to find the Lowest common ancestor in a DAG. A DAG can have scenarios where the LCA yields multiple solutions and I feel the accepted answer explains that pretty well.
However, one ...
- 131
3
votes
0
answers
371
views
Context-free grammar for DAGs?
I'm looking for a "safe" representation of DAGs. With "safe" representation I mean that it can be described by a context-free grammar. Ideally, this grammar would be suitable for a simple LR parser.
...
- 135
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.
- 1,331
2
votes
2
answers
139
views
What is the name of a rooted tree whose nodes may have edges to their descendants?
A tree is a special kind a graph.
However, I came across a data structure which is a like a rooted tree, but where nodes are authorized to have direct links to any of their descendants. Shortcuts if ...
- 123
2
votes
1
answer
315
views
Is the following figure DAG?
I have been through multiple definitions of DAG and all of them say that it is a directed graph without cycles. Also, it is said that it has topological ordering.
Now the following figure is directed ...
- 1,195
2
votes
2
answers
3k
views
Iterative Depth First Search for cycle detection on directed graphs
I found this pseudocode on Wikipedia, and looks very elegant and intuitive:
...
- 41
2
votes
1
answer
351
views
In a DAG, finding the path with the highest score
Given a directed, acyclic graph in which each node has an assigned integer score, what is a fast way of finding the path from a start and end vertex with the highest cumulative score? I thought of a ...
- 123
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
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
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
2
votes
1
answer
828
views
Does topological sort exist for any complete directed acyclic graph?
Let's assume that DAG is complete: there is directed edge among every to nodes. Does topological sort of vertices exist for any such graph? I.e. is it possible to make linear list of nodes in which ...
- 1,381
2
votes
1
answer
440
views
Find minimum set of vertices that are reachable from all other vertices
I have a DAG and I wish to find the minimal set of vertices that have a path to all other vertices.
My solution was to simply find all the vertices that their incoming degree is 0.
However, if there ...
- 23
2
votes
1
answer
63
views
What is an efficient algorithm to see if a set of nodes ultimately depend on a certain node in a DAG?
Hopefully this question makes sense. Basically, given a DAG, a set of nodes A, and another node b, I'd like to know if node b is an ancestor of any of the nodes in A in that graph.
This is my current ...
- 161