Questions tagged [topological-sorting]
Questions related to the topological sort or topological ordering problem, on directed acyclic graphs (DAGs) or partial orders
21
questions
6
votes
1
answer
495
views
Number of permutations that satisfy a given set of comparisons
We are given a set of comparisons of the form z[i] < z[j] for various i and j and an ...
0
votes
0
answers
179
views
Minimize Cumulative Cost on Topological Sort
We are given a n-vertex DAG $G=(V,E)$ and also given a cost function $c: V \rightarrow \Bbb N$.
Given a topological sort $S = v_1,v_2,...,v_n$, it has associated a sorting cost $S_c = \sum_{i=1}^{n} C(...
2
votes
0
answers
164
views
On-line pagerank in a streaming DAG (Directed Acyclic Graph)
Assume a DAG (Directed Acyclic Graph) is given as a stream of edges such that edge $(u,v)$ is given only after all incoming edges of $u$ are given. Let us denote by $n$ and $m$ the number of vertices ...
1
vote
0
answers
143
views
Reordering a DAG with the minimum changes
Consider a DAG $(V,A)$ with an initial permutation $(v_1,v_2,…,v_n)$. We want to arrange the $n$ vertices in topological order while keeping as many vertices as possible.
The problem is: Is it NP-...
3
votes
0
answers
144
views
Minimum feedback arc set for dense directed graph
This is really a matrix problem, but the theory I believe lies in graphs. Consider some matrix $A$ and permutation matrix $P$, where we define $\tilde{A}:= PAP^T$. I want to pick $P$ such that if $\...
6
votes
2
answers
444
views
find the most similar topological ordering of a dag
Given a permutation $L$ of the $n$ vertices of the directed acyclic graph $G=(V,E)$.
Question: is it NP-hard to find the topological order of the $G$ that is the most similar to the given permutation $...
5
votes
2
answers
530
views
Topological sorting of a DAG where special vertices have to come in even groups
Consider the following problem. The input is a directed acyclic graph (DAG) $G = (V, E)$, and a subset $V' \subseteq V$ of vertices, which we call special vertices. The question is to determine ...
3
votes
1
answer
198
views
how to achieve a topological sort of an given sequence with minimum swaps
For example, given the constraints {$a<b,c<d$} and a sequence $[b,a,c,d]$. we just need swap $a$ with $b$ to get an topological sort, I want to ask how to find the sort solutions with minimum ...
7
votes
1
answer
480
views
Computing topological sort while keeping edges "short"
Motivation: I want to compute a topological sort order in which the connected vertices are close to each other.
Problem statement: Given a DAG $G(V,E)$ with $n$ vertices, compute a topological sort ...
1
vote
1
answer
110
views
Constrained Topological Sorting with bounded number of chains
In general, constrained topological sorting is NP-hard.
Now we add another constraint to it, such that take any k+1 nodes and there will be at least one pair ...
8
votes
1
answer
2k
views
Minimum cost topological ordering
We are given a $n$ vertex directed graph $G=(V,E)$ and also given a cost function $c:V\times [n]\to \mathbb{R}$. Consider a topological ordering of the vertices, $v_1,\ldots,v_n$, the cost of the ...
5
votes
0
answers
242
views
NP-completeness of a specific topological sorting problem
Consider $(V, E)$ be a DAG, and $p_1, \dots, p_n$ be its topological sorting (i.e. such permutation $p$ of $V$ that $\forall(x, y) \in E.\ p^{-1}(x) < p^{-1}(y)$). Let's call the goodness of $p$ a ...
12
votes
2
answers
1k
views
Enumerating topological sorts of a vertex-labeled DAG
Let $G = (V, E)$ be a directed acyclic graph, and let $\lambda$ be a labeling function mapping each vertex $v \in V$ to a label $\lambda(v)$ in some finite alphabet $L$. Writing $n := |V|$, a ...
7
votes
1
answer
944
views
Ordering of a DAG minimizing some definition of cost
Consider a DAG $(V,A)$ with a topological ordering $(v_1,v_2,\ldots,v_n)$. I define the cost of this ordering as the maximum over all $1\leq i\leq n$ of $|\{j\leq i
\mid \exists k>i: (v_j,v_k)\in A\...
13
votes
2
answers
4k
views
Lexicographically minimal topological sort of a labeled DAG
Consider the problem where we are given as input a directed acyclic graph $G = (V, E)$, a labeling function $\lambda$ from $V$ to some set $L$ with a total order $<_L$ (e.g., the integers), and ...
3
votes
1
answer
717
views
Topological sort with alternative choices of predecessors
I have a family of directed graphs over the same set of nodes $V$ defined as follows.
Each node $v \in V$ has $k_v$ alternative choices for its set of predecessors. In other words, I am given a ...
36
votes
4
answers
3k
views
Why is "topological sorting" topological?
Why is "topological sorting" called "topological"? Is it just because it determines an order without altering any vertices or edges -- like a doughnut and coffee cup are topologically equivalent? Why ...
15
votes
3
answers
1k
views
Complexity of topological sort with constrained positions
I am given as input a DAG $G$ of $n$ vertices where each vertex $x$ is additionally labeled with some $S(x) \subseteq \{1, \ldots, n\}$.
A topological sort of $G$ is a bijection $f$ from the vertices ...
9
votes
2
answers
3k
views
Testing/Identifying a Topological Sorting
You're given a set of $n$ Directed Acyclic Graphs $G_1, G_2, ..., G_n$ over the same set of $m$ vertices $V$. You're also given a permutation of the set of vertices $(v_1,v_2,...,v_m)$. What is the ...
20
votes
4
answers
1k
views
Positive topological ordering, take 3
Suppose we have an n by n matrix. Is it possible to reorder its rows and columns such that we get an upper-triangular matrix?
This question is motivated by this problem:
Positive topological ordering
...
47
votes
5
answers
3k
views
Positive topological ordering
Suppose I have a directed acyclic graph with real-number weights on its vertices. I want to find a topological ordering of the DAG in which, for every prefix of the topological ordering, the sum of ...