15
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
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
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
I think this problem is NP-hard. I try to sketch a reduction from MinSAT. In the MinSAT problem we are given a CNF and our goal is to minimize the number of satisfied clauses. This problem is NP-hard, see e.g., http://epubs.siam.org/doi/abs/10.1137/S0895480191220836?journalCode=sjdmec
Divide the vertices into two groups - some will represent literals, the ...
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
[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
As Yury already mentioned, the output size can be too large to hope for subquadratic time, when measured as a function of the input size $n$. But even when the output size is small, very little can be done. In particular, suppose that the input is a partial order with a single comparable pair, chosen uniformly at random among all such partial orders. Then ...
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
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 ...
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
To start with the obvious: DAGs containing a Hamiltonian path, using the uniqueness of their topological orderings, and polytrees, as an orientation-labeled variant of trees.
On the other hand, it's tempting to list multitrees (as I did in an earlier incorrect version of this answer), using canonization of trees to prioritize their topological orderings, ...
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, ...
5
The main reason is that the non-constant degree would imply that the time per result is too high. The number of nodes found by the search, in the end, is going to be k, but all but the last one needs to have their children expanded, so the number of expanded nodes is kd where d is the degree. Unless d is O(1) this will be larger than the eventual time bound ...
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
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
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
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
