Skip to main content

# Tag Info

## Hot answers tagged topological-sorting

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 ...
• 9,517
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 ...
• 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 (...
• 9,517
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 ...
• 2,768
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 ...
• 342
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 ...
• 14k
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 ...
• 9,517
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.
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$. ...
• 14k
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 ...
• 9,517
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 ...
• 119

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