Questions tagged [dag]
For questions about the usage and manipulation of Directed Acyclic Graphs (DAG).
3
votes
1answer
59 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 ...
1
vote
1answer
33 views
Let G be a graph directed without circles. Suggest a method to find a minimum set of vertices So that all the vertices in the graph can be reached
Let G be a graph directed without circles. Suggest a method to find a minimum set of vertices
So that all the vertices in the graph can be reached.
I thought to run an SCC algorithm to find binding ...
1
vote
1answer
52 views
Can Dynamic programming be applied to solve problems if and only if the subproblem form a DAG?
I assume Dynamic Programming can be used only when the corresponding subproblems form a Directed Acyclic Graph, otherwise you're stuck in a loop.
Is this reasoning correct or is there more to it?
0
votes
1answer
18 views
There could not be an edge from u to v in a DAG, if w is before v in a topological order
I am trying to prove that given a DAG. There exists a valid topological ordering that has v in front of u iff there is no path from u to v. The proof is related to the fact that reverse DFS post ...
2
votes
1answer
80 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
...
2
votes
2answers
101 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 ...
2
votes
0answers
161 views
Finding unique topological ordering wrt to another vertex ordering
Given a directed acyclic graph with $n$ nodes labeled from $1$ to $n$, what is an efficient way to produce the unique topological ordering with lower labeled nodes prioritized over higher labeled?
...
1
vote
1answer
20 views
Extend reachability to total ordering
Given a finite DAG $G = (V, E)$ with $|E| \in \mathcal{O}(|V|)$, I want to compute a total ordering $<$ over $V$ that is compatible to reachability: If there is a transition $(u, v) \in E$, then $u ...
2
votes
1answer
51 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
vote
0answers
84 views
Topological sorting and NP-hard proof
I meet a problem. I can find a sub-optimal solution, but cannot find an optimal one and cannot prove its NPC hardness.
The problem can also be described as follows. Given a sequence $X=\{x_1,x_2,...,...
0
votes
1answer
282 views
DAG Hamiltonian Path NP-complete
The book computers and Intractability mentions that Hamiltonian Path problem is not NP-complete in DAG.
But if Hamiltonian Cycle is NP-complete in digraph then I can split a vertex and create two ...
2
votes
1answer
103 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 ...
0
votes
1answer
226 views
Longest path in a DAG: source to sink?
Is the longest path in a (weighted) DAG always from a source to a sink? This seems correct to me by intuition, but I'm not 100% confident. Like, for example, if I had an array in which each index ...
1
vote
0answers
30 views
DAGs and Equivalence Class of DAGs
I am learning DAGs and Equivalence Class of DAGs, I am reading the material by Prof. Campos Ibáñez here: https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume18/acid03a-html/node2.html
However, I ...
2
votes
0answers
148 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 ...
3
votes
1answer
3k 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 ...
2
votes
0answers
50 views
maximally exclusive paths in a DAG
Suppose we have a DAG $G$ with one source node $s$, ie. it has a path to every node, and target node $t$ which every node has a path to it. For a pair of paths from $s$ to $t$ we can define a distance ...
0
votes
1answer
115 views
How to tell if a spanning tree is a shortest-spanning tree of a DAG?
I know how to calculate the shortest paths from source s to all other reachable vertices in a DAG (with no negative weight on the edges)
By iterating the ...
2
votes
2answers
359 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 ...
0
votes
1answer
234 views
Flipping all incoming/outgoing edges from a vertex in a DAG
I'm working on a problem where I have a directed acyclic graph and I need to repeatedly flip all incoming (or outgoing, or both incoming and outgoing) edges from a single vertex. I think that ...
1
vote
0answers
246 views
Multithreaded algorithm to traverse DAG
I have a DAG of tasks designed as:
DAG {
Dictionary<NodeAddresses,Node>
}
Node {
List<Node> Parents;
List<Node> Children;
Task T;
}
...
3
votes
0answers
757 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 ...
3
votes
1answer
169 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 ...
1
vote
1answer
130 views
Approximating the dominating set on a certain kind of DAG
A dominating set on a directed graph $G=(V,E)$ is a subset $D$ of $V$ such that for all $v\in V$ it holds that $v\in D$ or there is an $u\in D$ such that $(u,v)\in E.$
For a concrete problem (size ...
0
votes
0answers
185 views
spanning tree of a DAG (directed acyclic graph) with less forward arcs
I am new to this algorithm and graphs. Just started learning. Could someone help me which algorithm is best suited to find the spanning tree of a Directed Acyclic Graph with less forward edges?
0
votes
0answers
144 views
In a DAG, what is the name for a vertex with only one predecessor and one successor?
In a directed acyclic graph (DAG), what is the name for a vertex with only one predecessor and one successor?
8
votes
1answer
382 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 ...
3
votes
0answers
216 views
Find all rooted subgraphs of a DAG
I searched the exchange and couldn't seem to find an answer to this.
I am trying to find an algorithm that, given a directed acyclic graph (DAG) $G = (N,E)$ with a single root node $r\in N$, finds ...
0
votes
1answer
278 views
In a DAG, longest path where every vertex has degree at most 2
I have a directed acyclic graph (DAG). How I can find the longest path using only vertices with degree at most 2?
Currently, I try this
...
2
votes
1answer
160 views
Minimum number of sets of unreachable vertices for directed acyclic graph (DAG)
I have a DAG with vertices $V$ and edges $E$. If $v,w \in V$ are vertices such that $v$ is not reachable from $w$ and $w$ is not reachable from $v$, I will say that $\langle v,w \rangle$ is an ...
0
votes
3answers
380 views
Topological Sort without modifying the graph or marking edges
I have a DAG which I want to traverse in a topological order. Wikipedia describes two algorithms for topological sorting, which both work in theory but seem impractical to me from a design point of ...
1
vote
0answers
186 views
Compression of a complete Directed Acylcic Graph
Consider a DAG $g$ as a label $l$ with a list of sub-nodes $\bar{g}$:
$g ::= l \enspace \bar{g}$
This is an "unfolded" representation of the DAG, i.e. it contains double entries, when two paths ...
3
votes
0answers
94 views
How do I merge these lists?
I ave a a collection of lists of objects:
$a_1$ $a_2$ $a_3$...
$b_1$ $b_2$ $b_3$...
$c_1$ $c_2$ $c_3$..
I need to merge them into a minimal possible number of lists, each list must be as long as ...
1
vote
0answers
138 views
Maximum weighted antichain over a DAG with cardinality constraint
Let $G=(V,E)$ be a vertex weighted DAG (Directed Acyclic Graph), with positive real valued weights.
Let also $k\leq \left\vert V\right\vert$, is there any way to find a maximum weighted antichain ...
0
votes
1answer
1k views
Longest path in DAG or finding DAG diameter
A directed acyclic graph (DAG), is a directed graph with no directed cycles.
That is, it consists of vertices and edges, with each edge directed from one vertex to another, such that there is no way ...
5
votes
1answer
285 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 ...
1
vote
0answers
72 views
Problem with update in Dynamic Bayesian Networks
Consider the following Bayesian network:
I want to impose constraints that state that a node can only be true (1) if at least one of its parents are true (1). So, for node $C$, the constraint takes ...
3
votes
1answer
99 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 ...
4
votes
0answers
183 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.
...
6
votes
0answers
126 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, ...
2
votes
1answer
38 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 ...
2
votes
1answer
332 views
Parse DAG into task tree
Suppose we have a DAG of tasks:
Arrows represent flow (reversed dependencies: 8 must be run after 7). Some of the tasks (like 4, 5, 6) can be run in parallel (Par block). Dependent tasks (like 7, 8, ...
4
votes
1answer
1k 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 ...
1
vote
1answer
448 views
SCC of a Directed Acyclic Graph
My instructor asked me to prove that strongly connected component of a DAG is also a DAG. I don't get it. How can a graph be DAG and strongly connected at the same time?
Consider a graph on two ...
5
votes
1answer
3k 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 ...
1
vote
0answers
98 views
Fully dynamic k-shortest-path
I have a directed acyclic graph with positive edge weights. It is constantly changing in that nodes are deleted and added. For each change, I need to find the $k$ shortest paths.
My current approach ...
4
votes
0answers
3k 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 ...
2
votes
0answers
110 views
Max Flow on low depth DAGs
I have a family of acyclic networks in which every path from the source of a given network to its target has length exactly $3$. I'm aware of a publication that in general, finding a max flow in a DAG ...
12
votes
4answers
6k 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 ...
