Questions tagged [dag]

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

Filter by
Sorted by
Tagged with
16 votes
4 answers
12k 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 ...
Karan's user avatar
  • 291
9 votes
1 answer
487 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)$...
Miel Sharf's user avatar
7 votes
1 answer
559 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 ...
bzliu94's user avatar
  • 372
7 votes
0 answers
469 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 ...
ryan's user avatar
  • 4,511
6 votes
1 answer
5k 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 ...
Median Hilal's user avatar
6 votes
1 answer
754 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 ...
hengxin's user avatar
  • 9,551
5 votes
1 answer
290 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)$, ...
andy_fingerhut's user avatar
5 votes
2 answers
13k 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 ...
SBDK8219's user avatar
  • 151
5 votes
1 answer
1k 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 ...
Sudix's user avatar
  • 709
5 votes
0 answers
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, ...
Nicola Gigante's user avatar
4 votes
3 answers
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 ...
Johntrik's user avatar
4 votes
1 answer
190 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 ...
Robert Rovetti's user avatar
4 votes
1 answer
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 ...
Eran Medan's user avatar
4 votes
1 answer
1k 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, ...
David's user avatar
  • 163
4 votes
0 answers
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 ...
Johannes's user avatar
4 votes
0 answers
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 ...
Loves Probability's user avatar
3 votes
1 answer
141 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 ...
chausies's user avatar
  • 532
3 votes
2 answers
920 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 ...
user72738's user avatar
3 votes
1 answer
71 views

Maximum Vertex Set With a Minimum Pairwise Distance Requirement in Directed Acyclic Graphs

Let $G=(V,E)$ be an unweighted directed acyclic graph with a set $V$ of vertices and a set $E$ of edges. The all-pairs shortest path problem can be solved efficiently using the Floyd-Warshall ...
Daniel García's user avatar
3 votes
1 answer
110 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 ...
EvaMGG's user avatar
  • 167
3 votes
2 answers
920 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: ...
ed94133's user avatar
  • 143
3 votes
1 answer
265 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 ...
DarkCave's user avatar
3 votes
1 answer
938 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 ...
gd1's user avatar
  • 133
3 votes
2 answers
2k 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 ...
Siddharth Joshi's user avatar
3 votes
1 answer
216 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 ...
jonem's user avatar
  • 371
3 votes
1 answer
75 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. ...
MSalters's user avatar
  • 895
3 votes
1 answer
179 views

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, ...
Philip L's user avatar
3 votes
1 answer
466 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 ...
YoursTruly's user avatar
3 votes
2 answers
216 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 ...
Michael Muré's user avatar
3 votes
1 answer
129 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 ...
Erel Segal-Halevi's user avatar
3 votes
1 answer
125 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 ...
Taytay's user avatar
  • 131
3 votes
1 answer
62 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 ...
Antimony's user avatar
  • 404
3 votes
1 answer
488 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 ...
Kunal Gupta's user avatar
3 votes
0 answers
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 ...
Alex Shpilkin's user avatar
3 votes
0 answers
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 ...
Gerard Yin's user avatar
3 votes
0 answers
121 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 ...
Johannes's user avatar
3 votes
0 answers
189 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 ...
Paul Accisano's user avatar
3 votes
0 answers
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 ...
Daniel's user avatar
  • 31
3 votes
0 answers
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 ...
aug's user avatar
  • 131
3 votes
0 answers
401 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. ...
vog's user avatar
  • 135
2 votes
1 answer
3k 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.
Teodor Dyakov's user avatar
2 votes
2 answers
146 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 ...
Clement's user avatar
  • 123
2 votes
1 answer
319 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 ...
Navjot Singh's user avatar
  • 1,215
2 votes
2 answers
4k views

Iterative Depth First Search for cycle detection on directed graphs

I found this pseudocode on Wikipedia, and looks very elegant and intuitive: ...
saifrim's user avatar
  • 41
2 votes
1 answer
383 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 ...
user1760791's user avatar
2 votes
2 answers
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 ...
David's user avatar
  • 121
2 votes
2 answers
376 views

DAG: When adding an edge that would normally result in a cycle, is there an algorithm to split the graph instead?

Summary I am using a DAG to compress a tree structure with many repeated nodes (the repeated nodes only very seldomly do not also have repeated edges out.) Normally, when attempting to add an edge to ...
OmnipotentEntity's user avatar
2 votes
2 answers
124 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 $...
taktoa's user avatar
  • 364
2 votes
1 answer
956 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 ...
TomR's user avatar
  • 1,401
2 votes
1 answer
448 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 ...
Myron's user avatar
  • 23