Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

2
votes
0answers
110 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 ...
0
votes
0answers
43 views

Efficient topological sorting of the cartesian product of DAGs

Let us consider n directed acyclic graphs $(G_i)_{1\leq i \leq n}$ and G their cartesian product (with the induced edges) : G is still a DAG. Let us suppose that each vertex has a value, defined as ...
-2
votes
1answer
98 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 ...
1
vote
0answers
63 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 ...
6
votes
1answer
211 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 ...
4
votes
0answers
71 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$ ...
5
votes
1answer
477 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 ...
2
votes
1answer
112 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 ...
1
vote
0answers
93 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 ...
2
votes
1answer
127 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
1answer
192 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 ...
-1
votes
1answer
88 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 ...
12
votes
1answer
269 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'...
2
votes
0answers
104 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 ...
4
votes
0answers
161 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 ...
11
votes
1answer
569 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 ...
6
votes
1answer
296 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\...
2
votes
0answers
365 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 ...
16
votes
1answer
575 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 ...
3
votes
1answer
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 ...
5
votes
0answers
655 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$ ...
13
votes
2answers
2k 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 ...
14
votes
1answer
367 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 ...
1
vote
1answer
73 views

What does the contention-free communication assumption really mean in the context of DAG scheduling?

In many papers about DAG (directed-acyclic graph) scheduling in distributed systems, the authors make the assumption that the communication between the processors of the system where the DAG is ...
1
vote
2answers
641 views

Shortest path in DAG with path dependent arc costs

I've got the following problem Consider a DAG $G=(V,E)$ with $V=[v_1,…,v_n]$, and edge-set $E=[e_1,…,e_m]$, with associated costs $c_1,…,c_m$. The problem is to find the shortest paths from an ...
9
votes
1answer
187 views

When does a graph admit an orientation in which there is at most one s-t walk?

Consider the following problem: Input: a simple (undirected) graph $G=(V,E)$. Question: Is there an orientation of $G$ satisfying the property that for every $s,t \in V$ there is at most one (...
27
votes
2answers
1k views

Why is “topological sorting” topological?

Why is "topological sorting" called "topological"? Is it just because it determines an order without altering any vertices or edges -- like a doughnut and coffee cup are topologically equivalent? Why ...
2
votes
1answer
135 views

An edge orientation procedure to generate all acyclic orientations of a graph

Consider the following scheme for enumerating acyclic digraphs (DAGs) by orienting the edges in an undirected graph $G$ with $n = ||V||$ vertices: (1) Generate all $n!$ possible permutations $p_i$ of ...
2
votes
0answers
127 views

Realization of a bipolar orientation by a mixed graph

Given an undirected graph $G(V,E)$ and a bipolar orientation $s$ over $G$, consider the problem of identifying $s$ by finding the minimum number of edges such that when orienting them in a particular ...
0
votes
0answers
107 views

Minimum Weight Ordering of nodes on a directed graph

I'm bumping my head against the wall trying to prove this problem is NP-complete (it might not be) Let $G = (V,E)$ be a directed graph with weights $w:E \to \mathbb{R_{\geq 0}}$ on the edges. The ...
5
votes
0answers
147 views

Indexing structure for all-pairs min-cuts in a huge DAG

I have a huge DAG - e.g., the dependency graph of all packages in a linux distribution. Suppose I'd like to make a user-friendly tool that makes it very easy to understand how to break the transitive ...
-1
votes
1answer
917 views

All pairs shortest paths in a DAG [closed]

I have studied the Floyd-Warshall and Johnson algorithms. I am trying to understand if the all pairs shortest paths research in a directed graph G can be implemented in a more efficient way if I ...
4
votes
0answers
768 views

K-path cover problem for a DAG

I am doing a little literature review and I was trying to know if, for a directed acyclic graph, the minimum k-path cover problem is solvable in polynomial time. A k-path cover is a set of paths with ...
7
votes
1answer
258 views

Complexity of counting poset automorphisms

A (finite) poset $P = (X, <)$, or partially ordered set, is a (finite) set $X$ equipped with a transitive antisymmetric relation $<$; it can be equivalently seen as a DAG $G = (X, E)$ that is ...
-4
votes
1answer
5k views

Efficient algorithm to create a directed dependency graph

I am looking for an efficient algorithm to create a graph like this: Initially the graph is filled with x then hs then ...
4
votes
0answers
125 views

Deciding transitivity of a directed acyclic graph [duplicate]

Is there any algorithm that decides whether a given directed acyclic graph is transitive or not, in time-complexity asymptotically better than boolean matrix multiplication?
9
votes
5answers
2k views

Transitivity check vs. Transitive Closure

Is checking transitivity of a digraph not easier than (in terms of asymptotic complexity) taking the transitive closure of the digraph? Do we know any lower bound better than $\Omega(n^2)$ to ...
3
votes
1answer
231 views

Maximize the expected number of “losers” - Is it NP-hard?

I am trying to find a reduction for a problem that seems NP-hard: Let me start from a toy example. Consider 3 elements, $a$, $b$, and $c$. You want to choose two pairs out of the three pairs and ...
1
vote
1answer
195 views

How to find the set of edges for the directed graph associated with a partial order?

I have a set $S$, and a partial order relation $\preceq$ defined on $S$. The way this partial order is given to me is through a function $f:S\times S \to \{true, false\}$, where $f(a,b) = true$ if ...
15
votes
3answers
850 views

Complexity of topological sort with constrained positions

I am given as input a DAG $G$ of $n$ vertices where each vertex $x$ is additionally labeled with some $S(x) \subseteq \{1, \ldots, n\}$. A topological sort of $G$ is a bijection $f$ from the vertices ...
9
votes
1answer
346 views

Finding optimal parallelization from general weighted undirected graph

I am solving a problem of "blending" sets of overlapping images. These sets can be represented by undirected weighted graph such as this one: Each node represents an image. Overlapping images are ...
7
votes
0answers
802 views

Partitioning DAG into Paths

What bounds (lower or upper) are known about the complexity of partitioning a Directly Acyclic Graph (DAG) into paths of respective sizes $n_1,\ldots,n_w$, such that to minimize their entropy $n{\cal ...
4
votes
0answers
986 views

Lowest Common Ancestor Problem in Directed Acyclic Graphs

What is the current best bound for the following problem in DAG: "For any pair of vertices in a given graph G, return all the LCAs of the same"? Edit: I am working on all-pair reachability problem in ...
4
votes
1answer
571 views

Multiple-sources dominator trees: compact representation and fast algorithm?

I recently learnt about the concept of dominator trees and was fascinated by it. I was wondering how the problem extends to computing dominators from multiple sources, or even from all vertices in ...
4
votes
0answers
399 views

Dynamic shortest path data structure for DAG

Let $G$ be a dynamic DAG (directed acyclic graph) where new vertices and new edges can be inserted. I am looking for an efficient data structure/algorithm to maintain the shortest path from a fixed ...
6
votes
1answer
227 views

Canonical labeling of special classes of DAGs

Graph Isomorphism of directed acyclic graphs (DAGs) is known to be GI-complete. So a polynomial time algorithm to canonize DAGs is not known. What are some special classes of DAGs that can be ...
3
votes
1answer
465 views

Breadth first search and Eppstein K shortest paths algorithm

I'm trying to understand the algorithm for finding K shortest paths in a graph described by Eppstein in this paper: http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf I have trouble particularly ...
5
votes
1answer
228 views

Revision Tracking Graph

Define the Revision Tracking Graph (RTG), which is an oriented graph (without circles) where each node x has a set C(x) associated with it. C(x) contains all edges on all paths from a node 0 ( C(0) = {...
27
votes
0answers
4k views

Combinatorics of Bellman-Ford or how to make cyclic graphs acyclic?

Roughly speaking, my question is: How costly is to make a cyclic graph acyclic while preserving all simple $s$-$t$ paths? Let $K_n$ be a complete undirected graph on vertices $\{0,1,\ldots,n+1\}$. (...
14
votes
1answer
547 views

Exact Algorithm for edge labeling problem in DAG

I am implementing some system part of which requires some help. I am therefore framing it as a graph problem to make it domain independent. Problem: We are given directed acyclic graph $G=(V,E)$. ...