Questions tagged [dag]
For questions about the usage and manipulation of Directed Acyclic Graphs (DAG).
66
questions
0
votes
1answer
29 views
Name for Turning DAG into redundant tree
I am looking for a term:
How is the tree called that you can obtain from a DAG by going top-down and appending all visited nodes to a tree, thereby copying nodes from the DAG into multiple occurences ...
2
votes
1answer
37 views
An algorithm for topological sorting based on depth-first search: why do we need two tags?
Wiki gives an alternative algorithm for topological sorting is based on depth-first search, as follows:
...
2
votes
1answer
33 views
Time complexity of finding a node with no incoming edges in a DAG: O(n) or O(m+n)
I'm reading Algorithm Design by Jon Kleinberg. In section 3.6, in order to compute the topological ordering of a DAG, one first finds a root node in this DAG, then deletes it from the DAG. The author ...
2
votes
1answer
31 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
vote
1answer
49 views
Extracting a spanning tree from a directed acyclic graph with minimum total distance between terminal nodes
I have a directed acyclic graph that has uniform edge weights. I would like to extract from this graph a spanning tree (an arborescence) with the property that the total distance between all pairs of ...
3
votes
1answer
186 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, ...
0
votes
0answers
41 views
Directed Acyclic Graph partition into minimum subgraphs with a constraint
I have this problem, not sure there is a name for it, wherein a Directed Acyclic Graph has different colored nodes. The idea is to partition it into minimum number of subgraphs with the following 2 ...
1
vote
1answer
39 views
Path of exact cost k in DAG
struggling with this question from an exam:
input:
DAG G=(V,E). each edge $e_i$ has weight $w_i\in \text{{0,1,2,3}} $
Two vertices : s,t
Number: k
output:
...
3
votes
0answers
78 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 ...
1
vote
0answers
26 views
Routing a DAG through 5 consecutive butterfly networks
I have two questions concerning the paper Nearly linear-size holographic proofs. In the second paragraph of section 6, A Graph Coloring Problem, it is claimed that
Using standard packet-routing ...
0
votes
0answers
34 views
Are these algorithms for detecting cycles in directional graph correct?
I want to detect whether a subset of a directional graph reachable from a given root has a cycle, and print some useful debug information about the cycle. It's not a problem if there's a cycle not ...
3
votes
2answers
83 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:
...
5
votes
0answers
97 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 ...
1
vote
0answers
70 views
Algorithm for finding single input/output sub graphs
I'm running into an interesting directed acyclic graph (DAG) problem and was wondering if this is a known problem and if it has an efficient algorithm for it. I will use 'graph' and 'DAG' ...
4
votes
0answers
84 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 ...
1
vote
1answer
30 views
Set of DAG vertices disconnecting a vertex from forbidden vertices
Let $v$ be a vertex with in-degree 0 in an (acyclic) DAG $G$, and let $F$ be a subset of $G$'s vertices (the "forbidden") vertices. Now suppose $U$ is a set of vertices such that every path from $v$ ...
1
vote
1answer
65 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 ...
4
votes
1answer
248 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
42 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
68 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
23 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
352 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
112 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
208 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
22 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
90 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 ...
2
votes
1answer
141 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
416 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
183 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
283 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
42 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
224 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
4k 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
53 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
257 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
547 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
328 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
305 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
998 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
275 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
146 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
214 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
193 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?
7
votes
1answer
432 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 ...
2
votes
0answers
296 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
330 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
191 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
471 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
244 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 ...
2
votes
0answers
95 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 ...
