Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [dag]

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

Filter by
Sorted by
Tagged with
3 votes
0 answers
49 views

Algorithm to find minimum number of cuts in DAG based on a rule

I encountered this problem while doing some “graph”ics programming: Take a directed acyclic graph where every vertex is given a non-unique label 1..N You can ‘trim’ the DAG by making a cut that ...
Matt Tytel's user avatar
0 votes
1 answer
21 views

Selecting an Induced Subgraph from a DAG with Specific Conditions

I am working with a Directed Acyclic Graph (DAG), denoted as $G$. The graph has a specific constraint where the out-degree of each vertex in $G$ is at most $2$. My objective is to select an induced ...
Ferran Gonzalez's user avatar
1 vote
0 answers
20 views

re-rooting a rooted DAG

A "network" is a DAG with a single source (the "root") and all nodes except the root either have in-degree one or out-degree one. A network is "binary" if all nodes have ...
igel's user avatar
  • 111
0 votes
0 answers
16 views

Are there any programs/libraries that can generate all acyclic digraphs on n vertices?

Are there any programs/libraries that can generate all unlabeled acyclic digraphs on n vertices? I'm thinking of something like Nauty's geng; but for DAGs. (I have ...
Zack's user avatar
  • 121
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
0 votes
0 answers
8 views

Profitable sequence in a $k$-partite DAG

This question is an extension of this one. Let $D(V, A)$ be a $k$-partite DAG; $P = \{ p_k : 1 \leqslant k \leqslant |P| \}$ such that $p_k \cap p_l = \emptyset$, $\forall k,l : k \neq l$, and $\...
Matheus Diógenes Andrade's user avatar
1 vote
1 answer
41 views

Shortest paths in $k$-partite DAG

Let $D(V, A)$ be a $k$-partite DAG; $P = \{ p_k : 1 \leqslant k \leqslant |P| \}$ such that $p_k \cap p_l = \emptyset$, $\forall k,l : k \neq l$, and $\bigcup_{1 \leqslant k \leqslant |P|} p_k = V$ ...
Matheus Diógenes Andrade's user avatar
1 vote
1 answer
37 views

Dynamic Programming as DAGs - Solution Always Shortest Path?

I've been trying to get a deeper understanding of how dynamic programming works and came across how it can be represented as directed acyclic graphs (DAGs). It's easy to see why, nodes represent the ...
Macroxela's user avatar
1 vote
0 answers
62 views

Total combinations in DAG with upper bound on node value

There is a directed acyclic graph with M edges. There is only one component (If they were undirected edges all nodes will be reachable will from one to another). An edge from a to b means value of ...
Aryan Agarwal's user avatar
2 votes
1 answer
59 views

Does the Nth iteration of Bellman-Ford relax every edge reachable from a negative cycle?

Consider a graph $G$ with $N$ nodes, with the distance of each node initially set to infinity (there is no start node). If there are no negative cycles in the graph, then after $N - 1$ iterations of ...
dav's user avatar
  • 123
1 vote
0 answers
38 views

Bucheim-Walker corollary for DCGs

The Bucheim-Walker algorithm is used for drawing trees. However, there are many real-world examples where Directed Cyclic Graphs would benefit from such an algorithm (e.g. family trees with ...
Sam's user avatar
  • 133
2 votes
0 answers
118 views

Finding highest value/weight ratio in dependency graph: NP-hard?

I have the following problem, and would like to figure out whether or not it's NP-hard - primarily to know that searching for a polynomial algorithm for it is futile. Approximations are possible, and ...
Pieter Wuille's user avatar
2 votes
1 answer
61 views

Non-dominated maximal paths in a DAG

Let $D(V, A)$ be a DAG. We call a dominated path in $D$ a path $P$ such that $P$ is maximal and $\exists P^{'} \in D . (P^{'} \text{ is maximal } \wedge V(P) \subset V(P^{'}))$ that is, $P$ is a ...
Matheus Diógenes Andrade's user avatar
1 vote
1 answer
143 views

How to find the learned clause from a UIP cut

I would guess that this question is going to make some people wonder how I haven't already found a solution looking through papers -- but I do not see a clear algorithm. In implementing CDCL, I read ...
Jack Sack's user avatar
0 votes
1 answer
134 views

Why not n^2 comparisons in the Alien Dictionary problem on leetcode?

Here's the problem statement (as given on GeeksForGeeks website): Given a sorted dictionary of an alien language having N words and k starting alphabets of standard dictionary, find the order of ...
Anurag Prasad's user avatar
0 votes
1 answer
38 views

Can a trie or DAWG loop?

I am looking at DAWGs, which are compressed tries, like this: It is an acyclic graph though, and I'm wondering if you are allowed to create loops or cycles in such a data structure. For example, I am ...
Lance's user avatar
  • 2,243
1 vote
1 answer
188 views

Minimum edges removed to turn a strongly connected graph into an acyclic graph

If I start with a directed graph that is strongly connected, is there a straightforward way / algorithm to find the smallest set of edges to remove, such that the result is a directed but acyclic ...
Daniel Cherno'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
2 votes
0 answers
90 views

Finding a maximum induced DAG in a digraph

I have a digraph D on n vertices formed in the following manner: I start with k ordered (not sorted) lists of integers, with each integer from 1-n in at least one list. Integers do not show up more ...
Dave's user avatar
  • 71
0 votes
1 answer
77 views

Correct Term for describing "diamond" subgraphs in a Directed Acyclic Graph

I am trying to research handling a specific type of possible subgraph in directed acyclic graphs. However, I am struggling to find the correct term to use. If we consider the subgraph S to be in a DAG ...
T-Tory's user avatar
  • 9
1 vote
0 answers
106 views

Topological sort of DAG that minimizes maximum number of unique-source-edges crossing through any node when placed in 1-d line

Consider a DAG such as one shown below: How do I find a particular topological order of nodes, such that when the nodes are placed in a straight line, the maximum number of unique-edges that cross ...
nepee's user avatar
  • 280
1 vote
0 answers
163 views

Reverse one edge to make the most expansive strongly connected component

Problem statement We're given a directed simple acyclic graph with weighted vertices. Find an edge $e$ such that reversing it would create a strongly connected component (SCC) whose price is maximal. ...
tomashauser's user avatar
0 votes
0 answers
27 views

Tree Width of Directed Graph

I'm Nestor Mermoz Thea. I have two definition over the Directed strong pseudoforest and Directed weak pseudoforest that I don't really well understand. Directed weak pseudoforest: A directed weak ...
Nestor Mermoz Thea's user avatar
3 votes
1 answer
283 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
1 vote
0 answers
140 views

Directed Acyclic Graph with minimized merging nodes

Suppose that we have a set of paths that all of them strat from the source "I" and end to the destination "O". The paths might have shared nodes. We are allowed to change the ...
Payam's user avatar
  • 11
1 vote
2 answers
190 views

reverse single edge in DAG and keep it a DAG

If I reverse a single edge in a DAG, how can I efficiently propagate the effects of that (e.g. change other edges) such that I don't introduce any cycles by said reversal? Is there a named algorithm ...
Brannon's user avatar
  • 127
0 votes
0 answers
114 views

Using topological sort to find inconsistencies represented by cycles in directed graphs

Consider the following scenario. Let $x_1,...,x_n$ be a group of cars that all drive from some point A to some point B. Each car starts driving in index order. i.e. $x_1$ starts driving strictly ...
user1da901's user avatar
-1 votes
1 answer
346 views

Converting a Directed Acyclic Graph to a Directed Tree

I'm wondering if anyone can help me with this. Say I have a DAG, I understand that it has no directed cycles, but it can have loops ( "diamonds" ). My question is, is there a known way to ...
T-Tory's user avatar
  • 9
0 votes
1 answer
300 views

Transitive Closure of a graph

Assuming we have a DAG, $G = (V, E)$, and we know that we can calculate $G$'s transitive closure in time complexity of $f(|V|, |E|)$, whereas $f$ is monotonic increasing function. Show that given a ...
PythonAddict's user avatar
0 votes
0 answers
104 views

DAG graph where indegree >= outdegree and indegree = 0 => outdegree <= 1, cover all vertex with min amount of paths

Given a graph $G = (V, E)$ where G is directed: $ \forall \ e \in E$ : $e$ has a direction. G is acyclic (no cycles): $ \forall$ path $v_1, \dots , v_n : (v_n, v_1) \not\in E $. If indegree $\gt0$, ...
borekking's user avatar
0 votes
1 answer
39 views

Name of this graph family?

Suppose I start with a directed chain graph of length $n$: And then I add $k$ edges, with a restriction that the result is a planar DAG: Is there a name for this graph family?
Yaroslav Bulatov's user avatar
1 vote
0 answers
17 views

Aggregating pairwise ratings in a graph

A finite set of individuals provide bounded non-binary pairwise ratings of other individuals (say, -10 to +10), forming a directed graph (cycles possible). I'd like to determine aggregate ratings for ...
vsekhar's user avatar
  • 111
3 votes
1 answer
76 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
0 votes
1 answer
2k views

modify dfs to find longest path

Let $G = (V, E)$ be a directed acyclic graph. Let every node $v \in V$ have an additional field $v_d$. For each vertex $v \in V$, we need to store in $v_d$ the length of the longest path in $G$ that ...
Redman's user avatar
  • 25
0 votes
0 answers
56 views

Minimise vertex loss converting DCG to DAG

I have a DCG that I want to lay out with the parents on the left and children to the right. I want to maximise the number of all children present to the right of all parents whilst minimising the ...
AJP's user avatar
  • 101
0 votes
0 answers
98 views

Dijkstra algorithm for DAG

Assuming we have a K-Partite DAG (edges are directed from one level to the next) with edge weights either 0, 1 or 2. We are looking for the shortest path between a node from group 0 to group k-1 (path ...
Philip L's user avatar
1 vote
0 answers
294 views

Determining whether DAG is semi-connected

I have been asked to write an algorithm which determine whether a DAG is semi-connected. (Recall that a DAG is semi-connected if for any pair of vertices $x,y$, there is either a path from $x$ to $y$ ...
NWiz95's user avatar
  • 11
1 vote
2 answers
287 views

Maximum flow in integer flow network

Let's say you have a maximum integer flow function in a network with 7 directed edges, meaning the flow cannot be increased anymore. The capacity of each edge is then increased by one. The capacity of ...
cyberspace's user avatar
1 vote
1 answer
196 views

Traversing a directed graph with negative weights

Let $G = (V, E)$ be a directed graph with negative edge weights and no cycles, and $L:V \to \mathbb [0, \infty[$ be a function defined over this graph. This graph represents all possible paths a ...
Rob32409's user avatar
  • 115
2 votes
1 answer
329 views

House Robber DP Algorithm (Not three in a row)

This is a similar question to A variant of the house robber problem but instead of the general case, I'm wondering how you would solve the standard house robber problem, but when you cannot rob from ...
JoeTheShmoe'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
3 votes
1 answer
969 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
2 votes
1 answer
426 views

Topological sort and finding longest path in DAG to solve a stacking boxes variation (no rotation)

Given n elements (boxes) I have to output the max number of boxes that can fit one into another. Each box has width (x), height (y) and depth (z). One box j can hold another box k if: ...
user avatar
0 votes
0 answers
108 views

Minimum weight $k-$path cover on a DAG proof verification

Suppose you are given a directed acyclic graph $G$ with $n$ vertices and an integer $k \leq n$. Each edge has an associated weight $w(u,v)$. We want to find $k-$vertex-disjoint paths that cover all ...
AspiringMat's user avatar
1 vote
1 answer
57 views

Given a list of comparisons, sort items with as few additional comparisons as possible

You have n items x[0], ..., x[n-1]. Beforehand, you're given a list of several comparisons ...
chausies's user avatar
  • 532
3 votes
1 answer
181 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
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
1 vote
0 answers
87 views

minimising Longest-Path in DAG

Assume we have weighted DAG (directed-acycle-graph), source s and target t. Define the number of edges as $E$. Given $0<\alpha<1$: Choose $\alpha*E$ edges to cut their weight by half so that the ...
Amran Tomer's user avatar
0 votes
0 answers
49 views

identify nodes with paths of unique length from source

Let us consider a Directed Acyclic Graph $G(V,E)$ such that all edges have unit weight. Let $s$ be a source node, $s\in V$ and a set of destination nodes, $D\in V\backslash s$. My problem is to find a ...
user49739's user avatar
0 votes
1 answer
236 views

DAG for contiguous subsequence of maximum sum

I have trouble understanding DAG behind the "contiguous subsequence of maximum sum problem". Let's say I denote by S(i) maximum of sums of contiguous ...
Awerde's user avatar
  • 113