# Questions tagged [dag]

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

134 questions
Filter by
Sorted by
Tagged with
11k views

### Transitive reduction of DAG

I am looking for O(V+E) algorithm for finding the transitive reduction given a DAG. That is remove as many edges as possible so that if you could reach v from u, for arbitrary v and u, you can still ...
• 291
402 views

### Shortest Path in a Directed Acyclic Graph with two types of costs

I am given a directed acyclic graph $G = (V,E)$, which can be assumed to be topologically ordered (if needed). Each edge $e$ in G has two types of costs - a nominal cost $w(e)$ and a spiked cost $p(e)$...
• 141
518 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 ...
• 362
4k views

### Finding all paths between a set of vertices in a DAG

Given a graph G= (V, E) that is: directed, acyclic, non-weighted, may have more than one edge between two vertices (thus, source and destination are not enough ...
• 393
218 views

### Algorithm for finding an irreducible kernel of a DAG in O(V*e) time, where e is number of edges in output

An irreducible kernel is the term used in Handbook of Theoretical Computer Science (HTCS), Volume A "Algorithms and Complexity" in the chapter on graph algorithms. Given a directed graph $G=(V,E)$, ...
985 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 ...
• 629
528 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 ...
• 9,179
304 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,361
136 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, ...
• 386
9k 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 ...
• 141
3k views

### Strongly connected components on a DAG

What is supposed to be the right result of an SCC algorithm running on a DAG. should it return "no components" or "there are V components of size 1"? I suspect it will return the latter (since it ...
• 421
94 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 ...
98 views

### Given an unsorted list of $n$ items, how many random comparisons are needed on average to be able to sort the list?

There is an unsorted list of $n$ items $x_1, \ldots, x_n$. Until you can sort the list, you are given one of the ${n \choose 2}$ possible binary comparisons uniformly at random (with replacement). On ...
• 389
818 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 ...
75 views

### Why do we use DAG rather than trees to represent search space of a search problem?

I saw people use DAGs to represent the search space of a search problems like the travelling salesman problem. Why is this better than the tree representation? Is the reason to save memory space on ...
• 165
88 views

### Is there a term for these "descendancy" subgraphs of directed acyclic graphs?

Consider a directed acyclic graph $G$ with vertex set $V$. Choose a vertex $v$, and let $H$ be the subgraph containing $v$ and all other vertices in $G$ that are reachable from $v$ (along with the ...
557 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: ...
• 143
362 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
1k 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 ...
163 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 ...
• 361
42 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. ...
• 799
142 views

• 364
576 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,351
367 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 ...
• 23
52 views

### What is an efficient algorithm to see if a set of nodes ultimately depend on a certain node in a DAG?

Hopefully this question makes sense. Basically, given a DAG, a set of nodes A, and another node b, I'd like to know if node b is an ancestor of any of the nodes in A in that graph. This is my current ...
• 161
198 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: ...
104 views

### edge coloring a directed acyclic graph

I have an edge coloring problem as follows: Suppose we have a DAG which has a source vertex s and an end vertex e, in addition, all the paths from s to e are of the same length say L. We define L ...
38 views

### Transitive reduction with vertex additions?

The transitive reduction of a (finite) directed graph is a graph with the same vertex set and reachability relation and a minimum number of edges. However, what if vertex additions are allowed? In ...
• 384