Questions tagged [directed-acyclic-graph]
This is a mathematical structure composed of a set of points or vertices and a set of connectors or edges. The edges connect the vertices and those vertices are directed. Also no cycles or in other words a directed edge that connects a vertex to a vertex are disallowed.
98
questions
0
votes
1
answer
67
views
What's the exact complexity of a DFS if we revisit nodes?
By "revisit nodes," I mean if we didn't maintain a set of nodes we have visited. So the sum I'm examining is just the number of paths from a root to a node, across all roots and nodes. We'll ...
- 13
1
vote
0
answers
21
views
Optimization: Turning a sparse graph of probabilities into the maximum likelihood DAG
I have a sparse matrix of probabilities that I want to turn into a DAG. If x[m,n] = pr it means that m is a descendent (direct or transitively) of n with probability pr. I want to construct a DAG over ...
- 111
1
vote
0
answers
38
views
Asking boolean question on the nodes of a DAG to find the target node
We are given a DAG $G=(V, E)$ and an unknown target node $x \in V$ to find. There is a mechanism to probe a node, $y \in V$, to ask question of the form "Given the node $y$, is the target node $x$...
- 11
0
votes
0
answers
66
views
Unclear explanation of basic parallel DAG computation
Consider computation represented as a DAG, without if-then-else conditions, where nodes represent tasks and edges represent data dependencies. For example, A->B->C means that there are 3 tasks ...
- 1
6
votes
1
answer
251
views
Complexity of reachability in directed rooted forests
I'm trying to figure out the complexity of the reachability problem having as input a directed rooted forest, i.e., given a set of directed rooted trees and two vertices $s$ and $t$, tell if $s$ and $...
- 133
0
votes
0
answers
174
views
Minimize Cumulative Cost on Topological Sort
We are given a n-vertex DAG $G=(V,E)$ and also given a cost function $c: V \rightarrow \Bbb N$.
Given a topological sort $S = v_1,v_2,...,v_n$, it has associated a sorting cost $S_c = \sum_{i=1}^{n} C(...
- 9
1
vote
0
answers
118
views
A reduction from the maximum $k$-closure problem to the clique problem
Fix a partially ordered set $(P, \le)$ with $N$ elements and real weights $w(p)$ for each $p \in P$. A subset $S \subset P$ is called closed if for any $x, y$ with $y \in S$ and $x \le y$ we also ...
- 111
2
votes
0
answers
155
views
On-line pagerank in a streaming DAG (Directed Acyclic Graph)
Assume a DAG (Directed Acyclic Graph) is given as a stream of edges such that edge $(u,v)$ is given only after all incoming edges of $u$ are given. Let us denote by $n$ and $m$ the number of vertices ...
- 693
5
votes
1
answer
573
views
Pagerank in directed *acyclic* graphs (DAG)
I deal with pagerank computations on large directed acyclic graphs (DAG).
I found no reference to work on this specific case, only some work on pagerank in more specific cases, e.g., PageRank of Scale ...
- 693
8
votes
1
answer
223
views
Monotone circuit representations of paths in a graph?
Consider a directed graph $G = (V, E)$ with a source $s \in V$ and sink $t \in V$. From $G$, I can define a monotone Boolean function $\phi_G$ on the set of variables $E$, in the following way: every ...
- 8,896
2
votes
1
answer
98
views
random sampling DAGs via nilpotent matrix sampling
The adjacency matrix of an acyclic graph is known to be a nilpotent matrix (all eigenvalues are zero). I am interested in sampling DAG adjacency matrices or equivalently sample random nilpotent ...
- 43
4
votes
1
answer
118
views
Survey on Erdős-Pósa?
Does anyone know of any good surveys on Erdős-Pósa?
I am particularly interested in what are the latest results for the bounding function for directed and even cycles in planar and minor free graphs ...
- 186
1
vote
0
answers
64
views
Directed tree decompositions on subtrees of DAGs
Given a DAG, is the arboreal decomposition of the DAG with the guarantee that given a node $x$, $v$ such that $x$ is reachable from $v$ are in the subtree of $x$? If not, is there a similar ...
- 23
2
votes
1
answer
420
views
Obtaining Sets of Ancestors Quickly in a Directed Acyclic Graphs
Suppose I have a DAG, $G = (V, E)$ and we know that all nodes in the DAG have at most $A$ ancestors. Let $V' \subseteq V$ be a subset of vertices of $V$. Is there a way to obtain the set of all ...
- 87
2
votes
0
answers
130
views
Finding nodes with enough unique ancestors
Given a DAG $G = (V, E)$, let $T \subseteq V$ be a set of nodes of $V$ that is computed via the following process. Assuming the nodes of $G$ are sorted in topological order, $v_1, \dots, v_n$. We ...
- 87
1
vote
1
answer
79
views
Separating DAGs using separators consisting of lists of nodes and all ancestors
Suppose we are given a DAG, $G = (V, E)$ where $n = |V|$. We consider the sets $J_1, J_2, \dots, J_n$ to be lists of vertices where list $J_i$ consists of vertex $v_i \in V$ and all ancestors of $v_i$....
- 87
1
vote
0
answers
117
views
reordering a DAG with the minimum changes
Consider a DAG $(V,A)$ with an initial permutation $(v_1,v_2,…,v_n)$. We want to arrange the $n$ vertice in topological order while keeping as many vertices as possible.
The problem is: Is it NP-hard ...
- 33
3
votes
0
answers
134
views
Minimum feedback arc set for dense directed graph
This is really a matrix problem, but the theory I believe lies in graphs. Consider some matrix $A$ and permutation matrix $P$, where we define $\tilde{A}:= PAP^T$. I want to pick $P$ such that if $\...
- 131
7
votes
1
answer
303
views
Isomorphism of ‘ordered’ DAGs / acyclic semiautomata
I am wondering what is known about the isomorphism problem on ordered DAGs, in particular how to find a canonical representative modulo isomorphism.
By ordered I mean that each vertex has a list of ...
- 273
1
vote
0
answers
85
views
Find all paths between specially paired nodes in a DAG in linear time
If I have a DAG with 2n nodes partitioned into n pairs of nodes with e edges, is there a ...
- 916
2
votes
1
answer
114
views
Complexity of acyclicity of a "nondeterministic" graph
By "nondeterministic" I mean the graph is a collection of sets of "candidate" edges sharing a single destination: $E \subseteq 2^V \times V$. The problem is whether it is possible ...
- 123
6
votes
2
answers
435
views
find the most similar topological ordering of a dag
Given a permutation $L$ of the $n$ vertices of the directed acyclic graph $G=(V,E)$.
Question: is it NP-hard to find the topological order of the $G$ that is the most similar to the given permutation $...
- 33
7
votes
1
answer
201
views
Is the isomorphism problem between posets represented by DAGs GI-complete?
Given two directed acyclic graphs, how hard is the problem of checking whether the partial orders they represent are isomorphic? Is this problem GI-complete?
I believe this problem is equivalent to ...
- 221
10
votes
1
answer
351
views
Lighting up all elements of a poset by toggling upsets
I consider the following game on a finite poset $(P, <)$. At each point of the game, I have a set of elements $S$ of the poset which are "on", and all others are "off". Initially $S = \emptyset$. ...
- 8,896
1
vote
1
answer
768
views
Breaking cycles in network graph by adding nodes and rerouting edges
I have a quite "common" need : making a directed graph (with one or several cycles) a directed acyclic graph (DAG).
But the way I want to achieve it is, I guess, way more specific : I would like to ...
- 119
1
vote
0
answers
64
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 ...
- 111
2
votes
0
answers
135
views
Common techniques for the acyclic orientation problem under some special constraint?
An acyclic orientation of an undirected graph is an assignment of a direction to each edge(an orientation) that does not form any directed cycle and therefore generates a directed acyclic graph(DAG). ...
- 461
1
vote
1
answer
4k
views
Number of simple paths between two vertices in a DAG
Let $G = (N, A)$ be a connected acyclic digraph (DAG). Furthermore, let $s \in N$ and $t \in N$ be two vertices on this graph, such that $t$ is reachable from $s$.
My problem is: how many simple $s-t$...
- 185
2
votes
0
answers
180
views
Crime prevention using graph theory and machine learning
I am looking for a way to the model the incidence of crime among a network of individuals. Part of it will use machine learning, and part of it will have to resort to some graph theoretic ...
- 149
-2
votes
1
answer
167
views
Finding Cheapest n-Path [closed]
Given a weighted directed acyclic graph, how can I find the cheapest path from an Origin Vertex to a Destination Vertex which ...
- 97
1
vote
0
answers
270
views
Directed NP Hard Problem on DAG
There are problems that are NP-Hard on undirected graphs(maximum weight independent set and graph coloring) but are polynomial time solvable on trees. Tree decomposition is a good tool to talk about ...
- 23
7
votes
1
answer
478
views
Computing topological sort while keeping edges "short"
Motivation: I want to compute a topological sort order in which the connected vertices are close to each other.
Problem statement: Given a DAG $G(V,E)$ with $n$ vertices, compute a topological sort ...
- 73
4
votes
0
answers
169
views
min weight k-closure on DAG
The problem
Given
a (connected) DAG $G(V,E)$ where each node is assigned an (non-negative) integer
weight
an integer k where $0\leq k\leq|V|$
Find a induced subgraph $H$ of $G$ consisting of $k$ ...
- 41
8
votes
1
answer
2k
views
Minimum cost topological ordering
We are given a $n$ vertex directed graph $G=(V,E)$ and also given a cost function $c:V\times [n]\to \mathbb{R}$. Consider a topological ordering of the vertices, $v_1,\ldots,v_n$, the cost of the ...
- 4,367
2
votes
1
answer
201
views
What is the name of this algorithm on direct acyclic graph?
I am trying to linearize the history of a git branch for display purpose. I want commits to be collocated by branch instead of simply displaying commits in the order given by the time of commit.
In ...
- 123
1
vote
0
answers
149
views
Generalized path cover problem in DAG
Let $G=(V,E)$ be a directed acyclic graph. Two vertices is transitive if there is a directed path between them. A Path Cover for a Set of Transitive Pairs (PCSTP) is a set of directed paths such that ...
- 11
2
votes
1
answer
428
views
Efficient algorithm for generating data dependency DAG from lists of memory ranges and access modes
Assume you are given:
A list of N (not necessarily distinct) memory ranges of the form [x,y], where x and y are non-negative integers representing the lower and upper bounds of the range, and
A list ...
0
votes
1
answer
1k
views
How to design an algorithm which turns an undirected graph into directed with all nodes of indegree higher than 0? [closed]
Given an undirected graph $G=(V,E)$ devise an algorithm that will check whether its edges can be directed in such a way that the vertices of the resulting directed graph will all have indegree higher ...
- 111
-1
votes
1
answer
121
views
Multiple source shortest path with one reversal [closed]
Lets say we have a directed graph G, with vertices V, that have lengths l.
I need to find the shortest path between every ordered pair of vertices in the graph, with the following constraint:
In a ...
11
votes
1
answer
501
views
Generalization of Dilworth's theorem for labeled DAGs
An antichain in a DAG $(V, E)$ is a subset $A \subseteq V$ of vertices that are pairwise unreachable, namely, there are no $v \neq v' \in A$ such that $v$ is reachable from $v'$ in $E$. From Dilworth'...
- 8,896
2
votes
0
answers
197
views
Two-player zero-sum games in extensive form represented as directed acyclic graphs
The following is a way to represent two-player zero-sum games in extensive form. Consider a directed acyclic graph $G$ where each non-terminal vertex is one of 3 types: player 1 vertex, player 2 ...
- 2,151
5
votes
0
answers
240
views
NP-completeness of a specific topological sorting problem
Consider $(V, E)$ be a DAG, and $p_1, \dots, p_n$ be its topological sorting (i.e. such permutation $p$ of $V$ that $\forall(x, y) \in E.\ p^{-1}(x) < p^{-1}(y)$). Let's call the goodness of $p$ a ...
- 191
12
votes
2
answers
1k
views
Enumerating topological sorts of a vertex-labeled DAG
Let $G = (V, E)$ be a directed acyclic graph, and let $\lambda$ be a labeling function mapping each vertex $v \in V$ to a label $\lambda(v)$ in some finite alphabet $L$. Writing $n := |V|$, a ...
- 8,896
7
votes
1
answer
927
views
Ordering of a DAG minimizing some definition of cost
Consider a DAG $(V,A)$ with a topological ordering $(v_1,v_2,\ldots,v_n)$. I define the cost of this ordering as the maximum over all $1\leq i\leq n$ of $|\{j\leq i
\mid \exists k>i: (v_j,v_k)\in A\...
- 251
5
votes
0
answers
966
views
Tree decomposition for DAGs
Tree decompositions and treewidth are a standard way to measure how close an undirected graph is to a tree. I am studying decompositions of directed acyclic graphs (DAGs), and have come to define them ...
- 8,896
18
votes
1
answer
1k
views
Reference for mixed graph acyclicity testing algorithm?
A mixed graph is a graph that may have both directed and undirected edges. Its underlying undirected graph is obtained by forgetting the orientations of the directed edges, and in the other direction ...
- 50.9k
3
votes
1
answer
1k
views
Longest path in a DAG that's not too long
The problem I am interested in is a simple variant of the longest path problem on DAGs: find a path between two chosen vertices in a DAG such that the sum of the weights of its constituent edges is ...
- 141
7
votes
0
answers
1k
views
Is there a linear-time algorithm for max flow on dags
What is the fastest known algorithm for max flow on dags?
Can there be a linear-time algorithm running in time $O(|V|+|E|)$?
Input: a weighted dag $G=(V,E,w)$ where
$E$ is given as an edge list $E$ ...
- 171
13
votes
2
answers
4k
views
Lexicographically minimal topological sort of a labeled DAG
Consider the problem where we are given as input a directed acyclic graph $G = (V, E)$, a labeling function $\lambda$ from $V$ to some set $L$ with a total order $<_L$ (e.g., the integers), and ...
- 8,896
16
votes
1
answer
512
views
How expensive may it be to destroy all long s-t paths in a DAG?
We consider DAGs (directed acyclic graphs) with one source node $s$ and one target node $t$; parallel edges joining the same pair of vertices are allowed. A $k$-cut is a set of edges whose removal ...
- 6,685