Questions tagged [dag]

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

Filter by
Sorted by
Tagged with
1
vote
0answers
50 views

What does a recursive min s,t-cut optimize?

Consider the following algorithm sketch: Given an edge-weighted directed acyclic graph $G = (V, E, w : E \to \mathbb{N})$, adjoin a temporary source $s$ and sink $t$ to get $G' = (V', E', w')$. $G'$ ...
1
vote
0answers
16 views

In a DAG, what is the name of the process replacing no branch path with a single vertex

In my work, I meet a process for DAG, and need to explain it in my report. So, I would like to know the name of the process. The process is very simple. The vertices of degree two except roots and ...
1
vote
2answers
88 views

Find every edge for which every s,t-path in a DAG goes through that edge

Given a connected sourced/sinked directed acylic graph $G = (V, E \subseteq V^2, s \in V, t \in V)$, we want to enumerate the edges $e \in \mathsf{Bottleneck}(G) \subseteq E$ for which every $s$,$t$-...
0
votes
0answers
28 views

Iterative Deepening DFS for DAGs

Does Iterative Deepening DFS only guarantee the shortest path for DAGs, assuming a visited list is used to prevent infinite cycles? I can't seem to find any answers online specifically related to ...
2
votes
2answers
79 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 $...
1
vote
0answers
47 views

Is there a data structure to represent changes to a DAG over time, with fast reproduction of instances of the DAG?

Consider a directed acyclic graph (DAG) of topics and links. Apart from the root topic, topics are situated under one or more parent topics, and links, as well, are situated under one or more parent ...
3
votes
1answer
61 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
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 ...
0
votes
1answer
23 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
44 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
102 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
39 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
92 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
23 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
104 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
31 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
22 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
120 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
340 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
115 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
55 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
50 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
29 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
39 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
191 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
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 ...
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
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 ...
0
votes
1answer
292 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" ...
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
112 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
290 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
155 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
70 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
154 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
405 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
70 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
56 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
36 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
50 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: ...
1
vote
1answer
244 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 ...