Questions tagged [dag]
For questions about the usage and manipulation of Directed Acyclic Graphs (DAG).
61
questions
0
votes
1answer
64 views
+50
Merging nodes of a DAG
I would like to merge connected nodes with a specific attribute of a directed acyclic graph.
After each merge operation, the graph should remain acyclic.
Let's say my graph contains blue nodes and ...
0
votes
0answers
32 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
34 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
68 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
23 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
27 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
73 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
78 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
62 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
83 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
27 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
62 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
198 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
40 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
65 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
21 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
217 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
110 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
184 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
74 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
132 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
387 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
166 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
266 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
38 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
201 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
178 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
497 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
298 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
294 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
888 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
253 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
143 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
196 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
184 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
419 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
267 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
323 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
184 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
443 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
228 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
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
154 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
2answers
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
339 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
74 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
105 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 ...
