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.

learn more… | top users | synonyms

21
votes
2answers
414 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 ...
1
vote
1answer
59 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 ...
1
vote
0answers
53 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
66 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 ...
4
votes
0answers
86 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 ...
-2
votes
1answer
129 views

Practical topological sorting for dependency graphs [closed]

I have been reading the Wikipedia page on Topological Sorting, specifically the depth-first algorithm which also detects cycles while it is building the sort. But from some experimentation with this ...
-1
votes
1answer
183 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
174 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
132 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 ...
-5
votes
1answer
369 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
119 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
606 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
206 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
131 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 ...
11
votes
3answers
489 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
267 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 ...
6
votes
0answers
332 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
516 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
436 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 ...
3
votes
0answers
260 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 ...
5
votes
1answer
163 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
267 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
197 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) = ...
24
votes
0answers
1k 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
499 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)$. ...
13
votes
1answer
1k views

Finding k shortest Paths with Eppstein's Algorithm

I'm trying to figure out how the Path Graph $P(G)$ according to Eppstein's Algorithm in this paper works and how I can reconstruct the $k$ shortest paths from $s$ to $t$ with the corresponding heap ...
11
votes
3answers
383 views

Efficient DAG comparison over a network

In distributed version control systems (such a Mercurial and Git) there is a need to efficiently compare directed acyclic graphs (DAGs). I'm a Mercurial developer, and we would be very interested in ...
2
votes
0answers
306 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 ...
0
votes
0answers
426 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, ...
3
votes
1answer
337 views

measures for a DAG (directed acyclic graph)?

Recently, I want to devise some kernelization (in the framework of parameterized complexity) for problem on DAG. So, find a proper parameter is essential. Well, is there a measure for the importance ...
3
votes
1answer
205 views

Shortest path in a DAG consisting of multiple copies of a smaller DAG

Let's say we have $k$ weighted DAGs (directed acyclic graphs) $$H_1 = (V_1, A_1), \dots, H_k = (V_k, A_k)$$ that are copies of one another. Now consider another weighted DAG $G$ that is built by ...
6
votes
0answers
203 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 ...
3
votes
3answers
515 views

A possibly new representation of DAGs

I had an idea for a way of representing DAGs, it's very easy to explain: Each node in the DAG is given an array of n integers. If it is possible to traverse from A to B then each of B's integers must ...
3
votes
1answer
283 views

Finding common label sequences in a directed acyclic graph

I have a directed acyclic graph with ~250k nodes, each node has one of about 100 symbols as label. Letting a word be the sequence of n symbols that corresponds to a path containing n nodes in the ...
17
votes
2answers
366 views

Does an algorithm exist to efficiently maintain connectedness information for a DAG in presence of inserts/deletes?

Given a directed acyclic graph, $G(V,E)$, is it possible to efficiently support the following operations? $isConnected(G,a,b)$: Determines if there is a path in $G$ from node $a$ to node $b$ ...
4
votes
2answers
225 views

Generation of unlabeled acyclic digraphs

I'm looking for an algorithm to efficiently generate all unlabeled acyclic digraphs of a given order. (By "unlabeled" I mean that no two of the generated digraphs should be isomorphic.) Thanks Edit: ...
8
votes
3answers
513 views

Route existence between n pairs of nodes

Given a directed acyclic graph with $2n$ nodes how can one determine if there is a path between any of following n pairs of nodes $(1 \rightarrow n+1), \ldots, (n \rightarrow n+n)$? There is a simple ...
8
votes
2answers
850 views

Testing/Identifying a Topological Sorting

You're given a set of $n$ Directed Acyclic Graphs $G_1, G_2, ..., G_n$ over the same set of $m$ vertices $V$. You're also given a permutation of the set of vertices $(v_1,v_2,...,v_m)$. What is the ...
-4
votes
1answer
405 views

Compact representation of DAG,

Given a DAG (which represents DDG – each node is a operation the in-edge/s show the operands from which inputs are taken) I want to obtain its compact representation of the graph, in such a way that: ...
1
vote
2answers
158 views

Special Properties Of DAWGs with Unique Elements

A DAWG is a specialized form of a Directed Acyclic Graph. Admittedly, not terribly specialized. I was wondering if DAWGs built from proper sets (unique, sorted) had any special properties? It seems ...
7
votes
3answers
1k views

Number of reachable vertices in DAG for every vertex

Let $G(V,E)$ be an acyclic directed graph, such that out-degree of any vertex is $O(\log{|V|})$. For every vertex of $G$ we can count the number of reachable vertices, just by running dfs from every ...
1
vote
0answers
1k 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: ...
11
votes
4answers
667 views

Directed NP-hard problems on DAGs

Tree width measures how close a graph is to a tree. Several NP-hard problems are tractable on graphs with bounded tree width. If a problem remains NP-hard on trees then tree width cannot save us. This ...
11
votes
1answer
523 views

Positive topological ordering, take 2

This is a followup to David Eppstein's recent question and is motivated by the same problems. Suppose I have a dag with real-number weights on its vertices. Initially, all of the vertices are ...
40
votes
5answers
2k views

Positive topological ordering

Suppose I have a directed acyclic graph with real-number weights on its vertices. I want to find a topological ordering of the DAG in which, for every prefix of the topological ordering, the sum of ...
30
votes
3answers
1k views

Given a weighted dag, is there an O(V+E) algorithm to replace each weight with the sum of its ancestor weights?

The problem, of course, is double counting. It's easy enough to do for certain classes of DAGs = a tree, or even a serial-parallel tree. The only algorithm I have found which works on general DAGs in ...