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.

28 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
30
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
554 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)$. ...
11
votes
1answer
697 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 ...
7
votes
0answers
177 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$. ...
7
votes
0answers
893 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 ...
6
votes
0answers
240 views

Restricted Reachability Problem

Let $G$ be a directed acyclic graph with $V$ vertices and $E$ edges. Choose some subset of $n\leq V$ "special" vertices $\{v_i\}_{i=1}^n$. How efficiently can we preprocess $(G, \{v_i\})$ so that we ...
5
votes
0answers
796 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$ ...
5
votes
0answers
154 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 ...
4
votes
0answers
97 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$ ...
4
votes
0answers
172 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 ...
4
votes
0answers
875 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 ...
4
votes
0answers
989 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
0answers
432 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 ...
2
votes
0answers
77 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). ...
2
votes
0answers
132 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 ...
2
votes
0answers
131 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
votes
0answers
463 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 ...
2
votes
0answers
133 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 ...
2
votes
0answers
336 views

Recursive parallel topological sorting in linear time

While doing some research on topological sorting I came across a paper Parallel Topological Sorting Algorithm, TADA, A. and MIGITA, M. and NAKAMURA, R. which claims a recursive divide-and-conquer ...
1
vote
0answers
50 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 ...
1
vote
0answers
98 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 ...
1
vote
0answers
114 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 ...
1
vote
0answers
451 views

Cycles in a directed graph

Wondering if we can prove the following or if it is already proved where can I get the proof. Let $v_1, v_2, v_3, \ldots, v_n$ and $t$ be $n+1$ vertexes in a directed graph. $v_1, v_2, v_3, \ldots, ...
1
vote
0answers
2k views

DAG partitioning to subgraphs

Given a DAG with $|V| = n$ and has $s$ sources, we have to present subgraphs such that each subgraph has approximately $k_1=\sqrt{s}$ sources and approximately $k_2=\sqrt{n}$ nodes. (Note: ...
0
votes
0answers
29 views

What is the current state of the art with respect to First Order Bayesian Networks?

The below is a survey paper: https://ieeexplore.ieee.org/document/5579472 Is there any significant updates to this? They mention Bayesian Logic Programs (BLP), Bayesian Logic (BLOG) and Multi-Entity ...
0
votes
0answers
42 views

2D-Interval partition problem

The classical interval partition Problem ascs for a minimal colouring of an interval graph: Let [a_i, b_i] be a collection of (closed) intervals (for i in {1,2,...,n} ). Find a partition of {1,2,...,n}...
0
votes
0answers
112 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 ...
-3
votes
1answer
6k 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 ...