Questions tagged [dag]
For questions about the usage and manipulation of Directed Acyclic Graphs (DAG).
107
questions
3
votes
1answer
51 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 ...
0
votes
1answer
16 views
Alternatives for finding sources in a DAG
I have a hard time seeing what the alternative approach is in linearizing a directed acyclic graph (DAG). Chapter 3 of Algorithms by Dasgupta et al. states:
Property Every dag has at least one source ...
0
votes
1answer
23 views
Vertices reachable from negative-weight cycles in Bellman-Ford
TLDR: I want to know if there's a simple way to fill in distances for all vertices reachable from negative weight cycles (not just ones on the cycle itself) once Bellman-Ford has found a negative-...
2
votes
2answers
93 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 ...
0
votes
0answers
16 views
What exactly are ancestors in DAG
I am new to graph theory and confused with ancestors definition in DAG(or in general graph).
For example in the following DAG
1--->2--->3<---4<---5
If ...
2
votes
0answers
37 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 ...
0
votes
0answers
18 views
Given start strings, find simplest DAG that constructs target strings by concatenation
Say we have a number of start strings (green) and a number of target strings (red). Two strings can always be concatenated to a new string which can then be arbitrarily often reused (two arrows in, (1,...
1
vote
1answer
53 views
If there is no Hamiltonian path in a DAG then there are at least two different Topological sorts
I understand the concept that if there is no Hamiltonian path so there will be 2 smaller paths and with them I can build more then one topological sort but I am not sure how make it formal.
Can you ...
0
votes
0answers
20 views
Transitive reductions of transitive closure
Is there a name for the relationship between two DAGs A,B where B is one of the transitive reductions of the transitive closure <...
0
votes
0answers
98 views
Methods for generating DAG with small Minimum Path Cover
On a directed acyclic graph $G=(V,E)$ the Minimum Path Cover (MPC) is the minimum number of paths that can be constructed on the DAG such that all vertices are covered by at least one path.
If one was ...
0
votes
1answer
24 views
Generating topological sequence from DAG with additional “not appearing before” constraints
DAG specifies the relationship of one node must appear after another. What if I add an additional constraint where one node cannot appear before another on top of the DAG?
Is there an algorithm for ...
1
vote
0answers
20 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 ...
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 ...
10
votes
1answer
296 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)$...
1
vote
1answer
93 views
Reference for counting the number of paths in a DAG
Given a connected DAG I know how to compute the number of paths between two nodes. See e.g. Counting number of paths between two vertices in a DAG .
Is there a reference or name for the algorithm? ...
1
vote
1answer
27 views
How can follow this this guide to construct a graph with matrix/reachability
Let's we have k matrices. For example we have 3 now, where first one is 8x5 ($a_1$ x $b_1$), second one is 5 x 6 ($a_2$ x $b_2$) and last one is 6 x 8 ($a_3$ x $b_3$). And our goal is to figure out ...
0
votes
2answers
51 views
Finding connected components without building the graph first
What are good algorithms for finding connected components in a graph defined by a set of elements X, where each x in ...
1
vote
2answers
35 views
Why is there so little literature on partial order production?
Please excuse or improve the poor title of this question.
My question is rather undirected, but I guess I am trying to find out if I might be missing a keyword for my problem.
So there is plenty of ...
1
vote
1answer
48 views
Best case “skew height” of an arbitrary tree
Given an arbitrary binary tree on $n$ nodes, choose an assignment $A$ from each parent to one of its children (the "favored child" as it were). We define the skew height of the tree as $H_A(\...
0
votes
0answers
27 views
2 Questions about Topological sorting in DAG
$G = (V,E)$ is a directed graph without cycles (DAG). Let $s,t \in V$ two vertices in the graph such that: exists a path from $s$ to any other vertex, and exists a path from any vertex to $t$.
...
1
vote
1answer
38 views
How to remove 'skip' edges from a DAG? (How to find only the longest path from each node to each of its sinks?)
In two separate projects, I have come across this problem and I still don't have a good solution for it, so I thought it was worth describing here. Consider the following problem:
I have a set of ...
1
vote
0answers
34 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 ...
0
votes
1answer
182 views
Given a tournament with $2^n$ vertices, show that there is a sub-tournament with at least $n + 1$ vertices that is acyclic
So a tournament is just a complete directed graph, I believe.
I'm having trouble proving this problem. I know it is induction however. I was thinking
the base case is $2^1$ vertices, and therefore ...
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 ...
3
votes
1answer
61 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 ...
1
vote
0answers
14 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 ...
2
votes
1answer
21 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 ...
0
votes
1answer
181 views
Why do we do topological sorting to find shortest or longest path in weighted DAG?
I was wondering why do we need to do the topological sort before performing relaxing of edges.
Wouldn't it'd be better if we do :
if starting vertex is "s"
...
0
votes
0answers
53 views
Least-weight path in a DAG--why not just use Dijkstra?
I have an assignment to find the least-weight path in a DAG from a source to a target. But the class has already discussed Dijkstra's algorithm, so I'm wondering, why not just use that? It seems too ...
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
83 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 ...
3
votes
1answer
283 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 ...
1
vote
0answers
111 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 ...
3
votes
1answer
62 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
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 ...
5
votes
1answer
137 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)$, ...
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.
0
votes
1answer
332 views
How to remove cycles from a directed graph by edge contraction?
We have cyclic directed graph (possibly disconnected). For cycles consisting of two vertices A->B and B->A, we replace them by a single vertex. In case of A->B, B->C, C->A we also replace them by one ...
1
vote
0answers
66 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 ...
3
votes
1answer
45 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 ...
0
votes
1answer
34 views
Topological Ordering
I have learnt to solve topological ordering using $in-degree$ method where we have to take the vertices having in-degree $0$ at an instance and arrange them in that order.
For example consider ...
0
votes
1answer
33 views
Name for Turning DAG into redundant tree
I am looking for a term:
How is the tree called that you can obtain from a DAG by going top-down and appending all visited nodes to a tree, thereby copying nodes from the DAG into multiple occurences ...
1
vote
1answer
49 views
An algorithm for topological sorting based on depth-first search: why do we need two tags?
Wiki gives an alternative algorithm for topological sorting is based on depth-first search, as follows:
...
2
votes
1answer
207 views
Time complexity of finding a node with no incoming edges in a DAG: O(n) or O(m+n)
I'm reading Algorithm Design by Jon Kleinberg. In section 3.6, in order to compute the topological ordering of a DAG, one first finds a root node in this DAG, then deletes it from the DAG. The author ...
2
votes
1answer
306 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
vote
1answer
79 views
Extracting a spanning tree from a directed acyclic graph with minimum total distance between terminal nodes
I have a directed acyclic graph that has uniform edge weights. I would like to extract from this graph a spanning tree (an arborescence) with the property that the total distance between all pairs of ...
3
votes
1answer
565 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, ...
0
votes
0answers
75 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 ...
1
vote
1answer
69 views
Path of exact cost k in DAG
struggling with this question from an exam:
input:
DAG G=(V,E). each edge $e_i$ has weight $w_i\in \text{{0,1,2,3}} $
Two vertices : s,t
Number: k
output:
...
3
votes
0answers
122 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 ...
