# Questions tagged [dag]

For questions about the usage and manipulation of Directed Acyclic Graphs (DAG).

61 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
468 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,511
137 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, ...
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
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 ...
34 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 ...
121 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
120 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
188 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 ...
547 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
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
399 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
112 views

### Finding highest value/weight ratio in dependency graph: NP-hard?

I have the following problem, and would like to figure out whether or not it's NP-hard - primarily to know that searching for a polynomial algorithm for it is futile. Approximations are possible, and ...
89 views

### Finding a maximum induced DAG in a digraph

I have a digraph D on n vertices formed in the following manner: I start with k ordered (not sorted) lists of integers, with each integer from 1-n in at least one list. Integers do not show up more ...
• 71
183 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 ...
• 203
257 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? ...
88 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 ...
640 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 ...
• 183
109 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 ...
• 121
120 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 ...
• 2,019
1 vote
62 views

### Total combinations in DAG with upper bound on node value

There is a directed acyclic graph with M edges. There is only one component (If they were undirected edges all nodes will be reachable will from one to another). An edge from a to b means value of ...
1 vote
37 views

### Bucheim-Walker corollary for DCGs

The Bucheim-Walker algorithm is used for drawing trees. However, there are many real-world examples where Directed Cyclic Graphs would benefit from such an algorithm (e.g. family trees with ...
• 133
1 vote
106 views

### Topological sort of DAG that minimizes maximum number of unique-source-edges crossing through any node when placed in 1-d line

Consider a DAG such as one shown below: How do I find a particular topological order of nodes, such that when the nodes are placed in a straight line, the maximum number of unique-edges that cross ...
• 280
1 vote
144 views

### Reverse one edge to make the most expansive strongly connected component

Problem statement We're given a directed simple acyclic graph with weighted vertices. Find an edge $e$ such that reversing it would create a strongly connected component (SCC) whose price is maximal. ...
• 129
1 vote
139 views

### Directed Acyclic Graph with minimized merging nodes

Suppose that we have a set of paths that all of them strat from the source "I" and end to the destination "O". The paths might have shared nodes. We are allowed to change the ...
• 11
1 vote
17 views

### Aggregating pairwise ratings in a graph

A finite set of individuals provide bounded non-binary pairwise ratings of other individuals (say, -10 to +10), forming a directed graph (cycles possible). I'd like to determine aggregate ratings for ...
• 111
1 vote
285 views

### Determining whether DAG is semi-connected

I have been asked to write an algorithm which determine whether a DAG is semi-connected. (Recall that a DAG is semi-connected if for any pair of vertices $x,y$, there is either a path from $x$ to $y$ ...
• 11
1 vote
87 views

### minimising Longest-Path in DAG

Assume we have weighted DAG (directed-acycle-graph), source s and target t. Define the number of edges as $E$. Given $0<\alpha<1$: Choose $\alpha*E$ edges to cut their weight by half so that the ...
1 vote
36 views

### How to compute all inequivalent (under Aut(P)) nonnegative integer weight assignments (with fixed sum) to the vertices of a finite poset P?

Let $P$ be a poset on $n$ points, $\text{Aut}(P)$ its automorphism group, and $a_1,a_2,\dots,a_k$ the lengths of the orbits under $\text{Aut}(P)$. Goal: An algorithm to generate a member from each ...
1 vote
67 views

### What does a recursive min s,t-cut optimize?

Consider the following algorithm sketch: Given an edge-weighted directed acyclic graph $G = (V, E, w : E \to \mathbb{N})$, adjoin a temporary source $s$ and sink $t$ to get $G' = (V', E', w')$. $G'$ ...
• 364
1 vote
20 views

### In a DAG, what is the name of the process replacing no branch path with a single vertex

In my work, I meet a process for DAG, and need to explain it in my report. So, I would like to know the name of the process. The process is very simple. The vertices of degree two except roots and ...
• 249
1 vote
99 views

### Is there a data structure to represent changes to a DAG over time, with fast reproduction of instances of the DAG?

Consider a directed acyclic graph (DAG) of topics and links. Apart from the root topic, topics are situated under one or more parent topics, and links, as well, are situated under one or more parent ...
• 111
1 vote
135 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
46 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 ...
• 11
1 vote
21 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 ...
• 159k
1 vote
546 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
177 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 ...
• 111
1 vote
33 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
234 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
186 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 ...
• 155
1 vote
55 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
424 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; } ...
• 111
1 vote
398 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 ...
• 610
1 vote
248 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
98 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 ...
• 371
1 vote
108 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 ...
• 111