# Questions tagged [dag]

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

113 questions
Filter by
Sorted by
Tagged with
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'$ ...
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 ...
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$-...
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 ...
79 views

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$. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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" ...
1k views

### Iterative Depth First Search for cycle detection on directed graphs

I found this pseudocode on Wikipedia, and looks very elegant and intuitive: ...
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 ...
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 ...
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 ...
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 ...
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 ...
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)$, ...
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.
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 ...
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 ...
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 ...
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 ...
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 ...