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 ...


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 ...


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 ...


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. ...


7

Yes, a valid ordering and a graph that goes with it can be found in polynomial time. I think it's easier to understand this if you look for the topological ordering first, and the graph second. What you are trying to find is an ordering of the vertices with the property that, for each vertex $v$, at least one of its predecessor sets appears in its entirety ...


5

This problem is NP-complete. I will prove NP-hardness below Source Problem Colored Token Swapping on Cliques: In the colored token swapping problem, we are given a graph with a colored token placed on each vertex. We are given the color of each token. Also, each vertex has a target color which is also given. A swap is an operation in which the tokens on ...


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 $...


3

The additional constraint amounts to saying that the input DAG has width $\leq k$, i.e., there is no antichain of size $k+1$. In this case, if $k$ is a constant, the decision version of the constrained topological sorting problem is in NL by Prop C.2 of https://arxiv.org/abs/1707.04310, which amounts to a PTIME dynamic programming algorithm. Reconstructing a ...


3

The problem you are calling "two-by-two" topological sorting is the Two Processor Scheduling Problem (unit-length jobs, under precedence constraints given by a partial order on the jobs -- i.e., the DAG). The partial order on the jobs constrains them so that if x<y then job y cannot be started until job x is completed. Shelling the vertices of the DAG ...


3

This paper, Obtaining a triangular matrix by independent row-column permutations Fertin, Rusu, and Vialette, shows that the problem is NP-complete for binary square matrices.


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 ...


2

A trivial observation is that if $|S(x)| \le 2$ for all $x$, then this problem is solvable in polynomial time, by reduction to 2SAT. Here's how. Introduce a variable $v_{x,i}$ for each vertex $x$ and each $i$ such that $i \in S(x)$. For each pair $x,y$ of vertices, if there is a path from $x$ to $y$, we get some constraints: if $i\in S(x)$, $j\in S(y)$, ...


2

Note that if you relax the problem by allowing $f$ to be arbitrary (not necessarily bijective), then it becomes polynomial. The algorithm proceeds similarly to topological sorting: you number the vertices one by one, maintaining the set $U$ of unnumbered vertices whose in-neighbors have been numbered. Whenever possible, you choose a vertex $x \in U$ and ...


1

OK, I'm coming back to this after some more thought based on the ideas of @GaraPruesse and @ChandraChekuri. I'm not 100% sure, because these arguments are a pain to formalize and visualize, but I think my problem of enumeration with special vertices coming in even groups (or in multiple-of-k groups) is in fact polynomially equivalent to the problem of two ...


Only top voted, non community-wiki answers of a minimum length are eligible