Questions tagged [dag]
For questions about the usage and manipulation of Directed Acyclic Graphs (DAG).
43
questions with no upvoted or accepted answers
5
votes
0answers
194 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 ...
5
votes
0answers
132 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, ...
4
votes
0answers
87 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 ...
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 ...
3
votes
1answer
56 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 information it ...
3
votes
0answers
90 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 ...
3
votes
0answers
113 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 ...
3
votes
0answers
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 ...
3
votes
0answers
264 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.
...
2
votes
0answers
25 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 ...
2
votes
0answers
231 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?
...
2
votes
0answers
298 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 ...
2
votes
0answers
59 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 ...
2
votes
0answers
367 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 ...
2
votes
0answers
99 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 ...
2
votes
0answers
116 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 ...
1
vote
0answers
18 views
Proof that “the last vertex in any postordering (in a DFS) of G lies in a source component of G”
From the book Algorithms (Jeff Erickson), there's a lemma that states:
The last vertex in any postordering of G lies in a source component
of G
My initial reaction to this was that the proof would ...
1
vote
0answers
33 views
Optimally find one of the total orderings for a poset based on some metadata about the elements
Given a finite, partially ordered set with the following two properties:
Every element in the set has one of two types: "A" or "B". The type does not define the total ordering of the set and is ...
1
vote
0answers
14 views
Shortest sequence of jobs, with dependencies, subject to capacity constraints
Suppose I have $n$ courses, some with some prerequisites, and I can take up to $k$ courses in a semester. I want to compute the least number of semesters needed to complete all courses, while ...
1
vote
0answers
79 views
Obtaining a graph with no cycles after removing k edges
I am looking for an algorithm that upon an input of a directed graph G and a natural number k,outputs a set of k edges, that upon removing them, the graph will have no cycles. If there are no such k ...
1
vote
0answers
65 views
Finding all non-comparable nodes in DAG
I have a DAG and I want to list all pairs of vertices that are not comparable (there is no path from the first to the second or the second to the first).
In this image (taken from this StackOverflow ...
1
vote
0answers
31 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 ...
1
vote
0answers
117 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' ...
1
vote
1answer
100 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 ...
1
vote
0answers
48 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 ...
1
vote
0answers
345 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;
}
...
1
vote
0answers
293 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 ...
1
vote
0answers
178 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 ...
1
vote
0answers
83 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 ...
1
vote
0answers
105 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 ...
0
votes
0answers
26 views
Algorithm for finding shortest set of paths through a weighted DAG (?)
Short version
What algoithm can find an optimal (or near optimal) solution to the following problem?
Given the following:
a weighted DAG, with one start node (only has outgoing edges) and one end ...
0
votes
0answers
17 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,...
0
votes
0answers
18 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 <...
0
votes
0answers
96 views
Methods for generating DAG with small Minimum Path Cover
On a directed acyclic graph $G=(V,E)$ the Minimum Path Cover (MPC) is the minimum number of paths that can be constructed on the DAG such that all vertices are covered by at least one path.
If one was ...
0
votes
1answer
23 views
Generating topological sequence from DAG with additional “not appearing before” constraints
DAG specifies the relationship of one node must appear after another. What if I add an additional constraint where one node cannot appear before another on top of the DAG?
Is there an algorithm for ...
0
votes
0answers
24 views
2 Questions about Topological sorting in DAG
$G = (V,E)$ is a directed graph without cycles (DAG). Let $s,t \in V$ two vertices in the graph such that: exists a path from $s$ to any other vertex, and exists a path from any vertex to $t$.
...
0
votes
0answers
36 views
Least-weight path in a DAG--why not just use Dijkstra?
I have an assignment to find the least-weight path in a DAG from a source to a target. But the class has already discussed Dijkstra's algorithm, so I'm wondering, why not just use that? It seems too ...
0
votes
0answers
75 views
Time complexity analysis of shortest path algorithm
Below is Dijkstra's algorithm from CLRS:
In the time complexity analysis of Dijkstra, CLRS says, RELAX() contains call to DECREASE-KEY(), which is essentially reducing edge weights associated with ...
0
votes
0answers
84 views
Find a longest path with k vertices in a directed graph
Given a weighted directed acyclic graph $G=(V,E)$, find a path (with $k$ vertices) so that the sum of edge-weights is maximum.
0
votes
0answers
71 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 ...
0
votes
0answers
36 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 ...
0
votes
0answers
254 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
208 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?
