Questions tagged [dag]

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

Filter by
Sorted by
Tagged with
15
votes
4answers
9k 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 ...
10
votes
1answer
323 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)$...
7
votes
1answer
491 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 ...
5
votes
1answer
147 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)$, ...
5
votes
1answer
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 ...
5
votes
1answer
455 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 ...
5
votes
0answers
220 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
2answers
7k 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 ...
4
votes
1answer
2k 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 ...
4
votes
1answer
585 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 ...
4
votes
0answers
88 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
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 ...
3
votes
1answer
60 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 ...
3
votes
1answer
66 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 ...
3
votes
1answer
50 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 ...
3
votes
2answers
354 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: ...
3
votes
2answers
964 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 ...
3
votes
1answer
142 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 ...
3
votes
1answer
351 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 ...
3
votes
1answer
117 views

How to detect “tree-able” set-families?

A set-family (a set of sets of elements) is called tree-able if the elements can be arranged on a directed tree such that each element appears in exactly one node, and each set in the family ...
3
votes
1answer
286 views

Construct a DAG from given multiple topological orderings

I need to construct a DAG, from its given topological orderings (i.e. the graph $G$ created must have all the orderings given as its topological orderings). For simplicity, the vertices are labeled as ...
3
votes
1answer
609 views

Merging nodes of a DAG

I would like to merge connected nodes with a specific attribute of a directed acyclic graph. The purpose is to detect max connected clusters of blue nodes and merge them. After each merge operation, ...
3
votes
1answer
59 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 ...
3
votes
1answer
62 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
94 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
127 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
279 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
1answer
2k views

Counting number of paths between two vertices in a DAG

I need an algorithm that computes the number of paths between two nodes in a DAG (Directed acyclic graph) I need a dynamic porgramming solution if possible.
2
votes
2answers
125 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
1answer
202 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
2answers
1k views

Iterative Depth First Search for cycle detection on directed graphs

I found this pseudocode on Wikipedia, and looks very elegant and intuitive: ...
2
votes
1answer
110 views

In a DAG, finding the path with the highest score

Given a directed, acyclic graph in which each node has an assigned integer score, what is a fast way of finding the path from a start and end vertex with the highest cumulative score? I thought of a ...
2
votes
2answers
739 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 ...
2
votes
2answers
75 views

Path graph partitioning, minimizing cut while minimizing maximum total node weight in each part

Suppose there is a path (linear) graph $G = (V, E)$ where $V = \{0, \ldots, n - 1\}$ and $E=\{(0, 1), (1, 2), \ldots, (n - 2, n - 1)\}$, with edge weights $w_e : E \to \mathbb{N}$ and vertex weights $...
2
votes
1answer
350 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 ...
2
votes
1answer
249 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 ...
2
votes
1answer
43 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 ...
2
votes
1answer
23 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 ...
2
votes
1answer
170 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,...,...
2
votes
1answer
255 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 ...
2
votes
1answer
607 views

Parse DAG into task tree

Suppose we have a DAG of tasks: Arrows represent flow (reversed dependencies: 8 must be run after 7). Some of the tasks (like 4, 5, 6) can be run in parallel (Par block). Dependent tasks (like 7, 8, ...
2
votes
2answers
98 views

Ordering of operations in a DAG of git commits

Context: I'm looking for a better state resolution algorithm for https://github.com/MichaelMure/git-bug Summary of the current algorithm and shortcomings git-bug is a distributed bug-tracker that ...
2
votes
0answers
38 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
2answers
27 views

When directed graph is linear, return the nodes in order. Otherwise fail

The Problem I have a set of edges (a, b), where a and b ...
2
votes
0answers
234 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
328 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
60 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
397 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 ...