12 votes
Accepted

Number of permutations that satisfy a given set of comparisons

As far as I can tell, your problem is equivalent to the following: given a partial order (represented by its comparability pairs, which forms a DAG), count how many linear extensions it has. This ...
a3nm's user avatar
  • 9,232
9 votes
Accepted

Computing topological sort while keeping edges "short"

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 ...
Gamow's user avatar
  • 5,772
9 votes
Accepted

Minimum cost topological ordering

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 (...
a3nm's user avatar
  • 9,232
5 votes
Accepted

how to achieve a topological sort of an given sequence with minimum swaps

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 ...
Mikhail Rudoy's user avatar
4 votes

Topological sorting of a DAG where special vertices have to come in even groups

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 ...
Gara Pruesse's user avatar
4 votes

Ordering of a DAG minimizing some definition of cost

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 ...
domotorp's user avatar
  • 13.8k
3 votes
Accepted

Constrained Topological Sorting with bounded number of chains

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 ...
a3nm's user avatar
  • 9,232
3 votes

Positive topological ordering, take 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.
Mohammad Al-Turkistany's user avatar
2 votes
Accepted

find the most similar topological ordering of a dag

It is NP-hard. The reduction is from $CLIQUE$, so suppose we are given an undirected graph $H$ on $n$ vertices and $m$ edges, with a parameter $k$, and our task is to decide whether $\omega(H)\ge k$. ...
domotorp's user avatar
  • 13.8k
1 vote

Topological sorting of a DAG where special vertices have to come in even groups

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 ...
a3nm's user avatar
  • 9,232
1 vote

Why is "topological sorting" topological?

Topology is the study of how "shapes" change when you apply continuous transformations to them. The central object of study is a topological space, which can be thought of as a way of saying ...
user513093's user avatar

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