19
The earliest reference I could find for topological sort is from [Lasser61]:
A network of directed line segments free of circular elements is assumed. The lines are identified by their terminal nodes and the nodes are assumed to be numbered by a non-topological system. Given a list of these lines in numeric order, a simple technique can be used to create ...
12
With multiple copies of the same label allowed, the problem is NP-hard, via a reduction from cliques in graphs. Given a graph $G$ in which you want to find a $k$-clique, make a DAG with a source vertex for each vertex of $G$, a sink vertex for each edge of $G$, and a directed edge $xy$ whenever $x$ is a vertex of $G$ that forms an endpoint of edge $y$. Give ...
11
Every simple path is uniquely determined by the subset of vertices that it passes through: if you topologically order the DAG (arbitrarily) then a path through any subset of vertices must go through those vertices in the same order given by the topological order. So (since $s$ and $t$ must always be included) there are at most $2^{n-2}$ paths.
This bound is ...
9
Below I'll show the following: if you have an O($n^{3-\varepsilon}$) time algorithm for checking if a graph is transitive for any $\varepsilon>0$, then you have an O($n^{3-\varepsilon}$) time algorithm for detecting a triangle in an $n$ node graph, and hence (by a paper from FOCS'10) you'd have an O($n^{3-\varepsilon/3}$) time algorithm for multiplying ...
9
It's NP-complete by a reduction from not-all-equal-3SAT. To see this, observe that
The only valid orientation of a $4$-cycle is one in which the edges alternate orientations.
Let $P$ be a three-edge undirected path, and add a degree-two vertex adjacent to the endpoints of $P$ to form a $5$-cycle. Then the only orientations of $P$ that can be extended to ...
9
Your problem is known under the name MINIMUM DIRECTED BANDWIDTH.
It is NP-complete:
M.R. Garey, R.L. Graham, D.S. Johnson and D.E. Knuth:
"Complexity Results for Bandwidth Minimization"
SIAM Journal on Applied Mathematics 34, (1978), pp. 477-495
It is problem [GT41] in the NP-completeness book by Garey and Johnson.
The special case where every ...
8
Your problem is NP-hard. I show this by a reduction from the shuffle problem: given words $w, w_1, \ldots, w_k$ over the alphabet $\{a, b, c\}$, decide whether $w$ can be obtained as an interleaving (aka "shuffle") of $w_1, \ldots, w_n$. This problem is NP-hard: see Warmuth & Haussler, On the complexity of iterated shuffle, JCSS, 1984, Theorem 3.1.
...
8
[Self answer; this is a shortened version, the old one can be found
here]
We realized with Georg Schnitger that the answer to my question is strongly negative: there are DAGs
(even of constant degree), where every $k$-cut must have a constant fraction of all edges, not just an about $1/k$ fraction, as in my question. (A slightly weaker result that a $1/\...
8
If you only need to order the outgoing edges the problem is GI complete. Reduce from GI of directed graphs. Given a digraph $D$ make a new one $D’$ as follows: Make a vertex in $D’$ for every vertex of $D$ and every arc of $D$. For every arc $u \rightarrow v$ of $D$, add the arcs: $uv \rightarrow u$ and $uv \rightarrow v$ in $D’$ (in this order). Clearly $D’$...
7
It looks like that $\Omega(n^2)$ is the best known lower bound, since any lower bound implies a lower bound for boolean matrix multiplication. We know that transitivity check can be achieved using one boolean matrix multiplication, that is, $G$ is transitive if and only if $G = G^2$.
7
With Charles Paperman we have been able to obtain such a result for DAGs labeled with the alphabet $\{a, b\}$. Essentially, we can show that given a DAG $G$ that has large antichains of $a$-labeled elements, large antichains of $b$-labeled elements, but no large antichains containing both many $a$-labeled and $b$-labeled elements, then there is a ...
7
The problem is L-complete.
It’s easier to think about it when the edges are written backwards. That is, I will consider the problem formulated as follows: given a directed acyclic graph such that every node has out-degree at most $1$, and vertices $s$ and $t$, determine if $t$ is reachable from $s$.
To see that it is in L, just follow the unique path ...
6
Without further information on how the costs can vary, the problem is NP-complete. For instance, consider the following rule for setting costs:
If an edge would return to a previously-traversed node then its cost is $n$
If an edge reaches $t$ without previously traversing all other nodes then its cost is $n$
In all other cases the cost of an edge is $1$.
...
6
Look at the graph that is formed by the comparisons. Each element corresponds to a vertex. If an element is a vertex of degree $d$, then the probability that it will be the lowest in at least one of these comparisons is the probability that it is not larger than all of its neighbors. This probability is $d/(d+1)$.
Now, expectation is linear. This means that ...
6
The best exact algorithm will run in time O( min{mn, n^2.38} ) by using fast binary matrix multiplication. However, there is a random algorithm, which runs in time O(m+n) and estimates the number of reachable nodes from each node with a small relative error, please refer to paper "Size-Estimation Framework with Applications to Transitive Closure and ...
6
Graph isomorphism is GI-complete for DAGs: https://en.wikipedia.org/wiki/Graph_isomorphism_problem#Complexity_class_GI.
The problem for partial orders is also GI-complete: We can reduce bipartite graph isomorphism (which is GI-complete) to 2 instances of DAG isomorphism where the DAG equals its transitive closure by considering two canonical ways to turn a ...
6
The strategy I outlined in the comment worked: reading through Bodirsky and Kara's paper, the first solvable case they consider is the case of min-closed languages, and your problem happens to fall into this category.
The algorithm they suggest is quite simple (in hindsight): look for a vertex $v_0$ which is never the target of any edge, and if you find one, ...
6
As suggested by the comments (thanks!), the answer is positive and rather easy.
We want to compute the pagerank of all vertices of a DAG (Directed Acyclic Graph) $G = (V,E)$ with $n$ vertices and $m$ edges. For any vertex $u$, let us denote by $d^+(u)$ its out-degree: $d^+(u) = |\{v, (u,v)\in E\}|$.
Pagerank is basically defined as the stationnary ...
5
I don't know about a survey, but I've found a recent PhD thesis, which seems to be well written:
Heinlein, Matthias (2019): Erdős-Pósa properties. Open Access Repositorium der Universität Ulm. Dissertation. http://dx.doi.org/10.18725/OPARU-11828
The first chapter gives a summary of the problem, known proof techniques and provides references to recent ...
4
Pseudocode for Eppstein's algorithm (and the authors' lazy version of it) are given in:
V.M. Jiménez, A. Marzal, A lazy version of Eppstein’s shortest paths algorithm, in: 2nd International Workshop on Experimental and Efficient Algorithms (WEA ’03), in: Lecture Notes in Computer Science, vol. 2647, Springer, 2003, pp. 179–190.
https://pdfs.semanticscholar....
4
Graph isomorphism for bipartite graphs is as hard as graph isomorphism for general undirected graphs. Considering bipartite posets (i.e., seeing bipartite graphs as Hasse diagrams of posets), you may see that counting the automorphisms of bipartite posets is as hard as counting the automorphisms of general undirected graphs.
4
Figuring if a DAG is transitive is as hard as deciding if a general digraph is transitive (which bring us back to your previous question :) ).
Assume you have an algorithm running in time $O(f(n))$ for deciding if a DAG is transitive.
Given a directed graph $G$, you can use the following randomized algorithm to decide if $G$ is transitive in time $O(f(n)\...
4
This problem is NP-complete, as the following reduces to it:
https://cstheory.stackexchange.com/a/1936/419
The sketch of the reduction is as follows.
From a set of tasks $T$ with $n$ tasks and some costs (not to be confused with your cost function!), we will make a DAG that has $N$ indegree 0 vertices (sources), and $N$ outdegree 0 vertices (sinks), where $...
4
Looks to me like some additional restrictions on a topological sort: https://en.m.wikipedia.org/wiki/Topological_sorting .
Also git already supports this operation for instance git rev-list --topo-order .
4
In this answer i assume that $u$ is an ancestor of $v$ if $u$ can reach $v$ by a directed path.
This is basically as hard as Set Cover (Given family $F$ over a universe $U$, find smallest subfamily $F’$ of $F$ whose union is $U$). To reduce from Set Cover:
Make a vertex for every set in $F$ and for every element in $U$. Make an arc from every element to ...
3
Edit: modified to emphasize how this approach can be generalized to any arbitrary degree sequence of lower bound in-degrees.
(Apologies if the below is extra verbose -- you said that you're new to graph algorithms, and I want to make sure you can follow the reasoning.)
Your problem is a special case of the Santa Clause problem, and the (significantly) more ...
3
This problem is Feedback Vertex Set in disguise, and hence NP-Hard, but I'd imagine there are good heuristics out there (I don't know the references myself, maybe someone can help me out here).
More specifically, for an input graph $G = (V, E)$ with minimal FVS $S \subseteq V$, there is a solution to your problem that copies each member of $S$ once (and no ...
2
The procedure maps each permutation of the vertices to some orientation of the graph whose topological ordering of the vertices is consistent with the permutation.
Every acyclic orientation of the graph induces at least one topological ordering of the vertices.
Every topological ordering of the vertices induces exactly one orientation of the graph (since ...
2
According to this reference (1), the lexicographically first topological order problem is NLOG-complete.
You may want to take a more thorough look at the article to ensure that it covers the case(s) that you're interested in. In particular, based on the technical report version (pdf) of that article, it appears that they're treating the lexicographic ...
Only top voted, non community-wiki answers of a minimum length are eligible