# Questions tagged [dag]

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

166 questions
Filter by
Sorted by
Tagged with
16 views

### Subgraphs of DAG minimizing overlap

Given a DAG, it has a number of 'source' nodes - nodes whose in-degree is zero. Each source node has a set of nodes reachable from it. I would like to partition the source nodes into $k$ disjoint ...
• 111
1 vote
49 views

### Version of SSSP

Let $G=(V,E)$ a directed graph s.t $|V|=n$. Let $w:E \to \mathbb{R}$ a weight function. Describe an algorithm which finds the minimal-weighted walk of length $\leq n$ from $s \in V$ to all other nodes....
32 views

### What is this graph?

I am seeking nomenclature to describe the family of graphs detailed below, and literature about its processing, traversal, costs, etc. Any and all input is welcome, e.g. papers, textbooks, helpful ...
• 111
1 vote
39 views

1 vote
44 views

### Shortest paths in $k$-partite DAG

Let $D(V, A)$ be a $k$-partite DAG; $P = \{ p_k : 1 \leqslant k \leqslant |P| \}$ such that $p_k \cap p_l = \emptyset$, $\forall k,l : k \neq l$, and $\bigcup_{1 \leqslant k \leqslant |P|} p_k = V$ ...
111 views

### Dynamic Programming as DAGs - Solution Always Shortest Path?

I've been trying to get a deeper understanding of how dynamic programming works and came across how it can be represented as directed acyclic graphs (DAGs). It's easy to see why, nodes represent the ...
1 vote
65 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 ...
61 views

### Does the Nth iteration of Bellman-Ford relax every edge reachable from a negative cycle?

Consider a graph $G$ with $N$ nodes, with the distance of each node initially set to infinity (there is no start node). If there are no negative cycles in the graph, then after $N - 1$ iterations of ...
• 123
1 vote
42 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
128 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 ...
63 views

### Non-dominated maximal paths in a DAG

Let $D(V, A)$ be a DAG. We call a dominated path in $D$ a path $P$ such that $P$ is maximal and $\exists P^{'} \in D . (P^{'} \text{ is maximal } \wedge V(P) \subset V(P^{'}))$ that is, $P$ is a ...
1 vote
200 views

### How to find the learned clause from a UIP cut

I would guess that this question is going to make some people wonder how I haven't already found a solution looking through papers -- but I do not see a clear algorithm. In implementing CDCL, I read ...
159 views

### Why not n^2 comparisons in the Alien Dictionary problem on leetcode?

Here's the problem statement (as given on GeeksForGeeks website): Given a sorted dictionary of an alien language having N words and k starting alphabets of standard dictionary, find the order of ...
50 views

### Can a trie or DAWG loop?

I am looking at DAWGs, which are compressed tries, like this: It is an acyclic graph though, and I'm wondering if you are allowed to create loops or cycles in such a data structure. For example, I am ...
• 2,275
1 vote
262 views

### Minimum edges removed to turn a strongly connected graph into an acyclic graph

If I start with a directed graph that is strongly connected, is there a straightforward way / algorithm to find the smallest set of edges to remove, such that the result is a directed but acyclic ...
1k views

### Linear-time algorithm for determining the presence of incomparable pairs in a directed acyclic graph (DAG)

I am seeking a linear-time algorithm to determine whether a directed acyclic graph (DAG) contains at least one pair of incomparable nodes. Two nodes $u$, $v$ are said to be incomparable if there is ...
• 43
91 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
88 views

### Correct Term for describing "diamond" subgraphs in a Directed Acyclic Graph

I am trying to research handling a specific type of possible subgraph in directed acyclic graphs. However, I am struggling to find the correct term to use. If we consider the subgraph S to be in a DAG ...
1 vote
109 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 ...
• 292
1 vote
172 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
27 views

### Tree Width of Directed Graph

I'm Nestor Mermoz Thea. I have two definition over the Directed strong pseudoforest and Directed weak pseudoforest that I don't really well understand. Directed weak pseudoforest: A directed weak ...
317 views

### Getting all vertices with fixed index in their topological ordering of a DAG

During my self study for graphs, I'm currently learning about topological sorting and ran into a question I'm not sure how to solve. There are typically more than one order of a topological ordering ...
• 43
1 vote
144 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
215 views

### reverse single edge in DAG and keep it a DAG

If I reverse a single edge in a DAG, how can I efficiently propagate the effects of that (e.g. change other edges) such that I don't introduce any cycles by said reversal? Is there a named algorithm ...
• 127
116 views

### Using topological sort to find inconsistencies represented by cycles in directed graphs

Consider the following scenario. Let $x_1,...,x_n$ be a group of cars that all drive from some point A to some point B. Each car starts driving in index order. i.e. $x_1$ starts driving strictly ...
407 views

### Converting a Directed Acyclic Graph to a Directed Tree

I'm wondering if anyone can help me with this. Say I have a DAG, I understand that it has no directed cycles, but it can have loops ( "diamonds" ). My question is, is there a known way to ...
347 views

### Transitive Closure of a graph

Assuming we have a DAG, $G = (V, E)$, and we know that we can calculate $G$'s transitive closure in time complexity of $f(|V|, |E|)$, whereas $f$ is monotonic increasing function. Show that given a ...
108 views

### DAG graph where indegree >= outdegree and indegree = 0 => outdegree <= 1, cover all vertex with min amount of paths

Given a graph $G = (V, E)$ where G is directed: $\forall \ e \in E$ : $e$ has a direction. G is acyclic (no cycles): $\forall$ path $v_1, \dots , v_n : (v_n, v_1) \not\in E$. If indegree $\gt0$, ...
40 views

### Name of this graph family?

Suppose I start with a directed chain graph of length $n$: And then I add $k$ edges, with a restriction that the result is a planar DAG: Is there a name for this graph family?
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
85 views

### When inserting a new vertex in a DAG, what possible changes are there to the edges

Background: I'm trying to program a generic method to add a node to a Directed Acyclic Graph. This method should allow the caller to specify the possible effects on the graph, specifically the edges. ...
• 905
2k views

### modify dfs to find longest path

Let $G = (V, E)$ be a directed acyclic graph. Let every node $v \in V$ have an additional field $v_d$. For each vertex $v \in V$, we need to store in $v_d$ the length of the longest path in $G$ that ...
• 25
58 views

### Minimise vertex loss converting DCG to DAG

I have a DCG that I want to lay out with the parents on the left and children to the right. I want to maximise the number of all children present to the right of all parents whilst minimising the ...
• 101
106 views

### Dijkstra algorithm for DAG

Assuming we have a K-Partite DAG (edges are directed from one level to the next) with edge weights either 0, 1 or 2. We are looking for the shortest path between a node from group 0 to group k-1 (path ...
• 23
1 vote
305 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
307 views

### Maximum flow in integer flow network

Let's say you have a maximum integer flow function in a network with 7 directed edges, meaning the flow cannot be increased anymore. The capacity of each edge is then increased by one. The capacity of ...
1 vote
198 views

### Traversing a directed graph with negative weights

Let $G = (V, E)$ be a directed graph with negative edge weights and no cycles, and $L:V \to \mathbb [0, \infty[$ be a function defined over this graph. This graph represents all possible paths a ...
• 115
362 views

### House Robber DP Algorithm (Not three in a row)

This is a similar question to A variant of the house robber problem but instead of the general case, I'm wondering how you would solve the standard house robber problem, but when you cannot rob from ...
• 195
2k views

### Can you use Dijkstra's algorithm to find the maximum cost path?

Suppose you have a DAG and the edges are positively weighted, and you want to find the maximum cost path from any node with no in degree to any node with no out degree. Is it possible to negate all ...
• 121
1k views

### Maximum number of distinct nodes that can be visited on a single walk

Given a directed graph which may contain cycles, how can I find the maximum number of distinct nodes that can be visited on a single walk? I have done some research and the most similar-sounding ...
• 133
457 views

### Topological sort and finding longest path in DAG to solve a stacking boxes variation (no rotation)

Given n elements (boxes) I have to output the max number of boxes that can fit one into another. Each box has width (x), height (y) and depth (z). One box j can hold another box k if: ...
111 views

### Minimum weight $k-$path cover on a DAG proof verification

Suppose you are given a directed acyclic graph $G$ with $n$ vertices and an integer $k \leq n$. Each edge has an associated weight $w(u,v)$. We want to find $k-$vertex-disjoint paths that cover all ...
• 613
1 vote
57 views

### Given a list of comparisons, sort items with as few additional comparisons as possible

You have n items x[0], ..., x[n-1]. Beforehand, you're given a list of several comparisons ...
• 542
### Partition of a $k$-partite graph to minimal number of connected sets
Let $G$ be a $k$-partite directed acyclic graph where the edges are only between two adjacent sets of vertices. I'm trying to partition the graph to the minimal number of connected sets. Sets \$A_0, ...