Is the optimal order of graph vertices s.t. minimizes edges to later vertices a well-known problem? I'm a little unfamiliar with graph theory, and I found an interesting problem in my work that I do not know if its already well-known or can be easily mapped to another one. If I were to express the problem more formally:

Given a directed unweighted graph $\langle V,E \rangle$, find a total order between vertices $v_1 &lt; v_2 &lt; \dots &lt; v_n$ such that minimizes $\vert F \vert$, where $F = \{ \langle v_i,v_j \rangle \ \vert\ v_i &lt; v_j , \langle v_i,v_j \rangle \in E \}$. That is find a total order between vertices such that it minimizes the number of edges that go "forward" in the order.

Lets suppose a simple directed graph:



The list of edges would be $[ a \rightarrow b $, $b \rightarrow c$, $a \rightarrow c ]$.

A bad order would be  $b &lt; a &lt; c$, because, for example, $c$ comes after $b$ in the order and we have the edge $b \rightarrow c $. Therefore, $F = \{ \langle b,c \rangle , \langle a,c \rangle \}$, $\vert F\vert = 2$.

A good order would be $c &lt; b &lt; a$, because $b &lt; a$ and $c &lt; b$. This gives $F = \emptyset$ and therefore the optimum: $\vert F\vert = 0$.

I have graphs that are dense, with some strongly connected components, and when trying to solve it using a SMT solver it works really bad with non-trivial instances. My intuition says that it's like a pigeonhole problem. So, my questions are:


Is this a well-known problem in the graph-theory community?
Can be easily mapped to any other problem?
If so, there is any good algorithm to solve it?
Can a good heuristic be computed easily?


Many thanks in advance :)
Your problem can be mapped to problem of finding minimal set of edges $F$ such that $G\backslash F$ is a DAG (each solution for your problem is a solution for this problem and vice versa). This problem is known as minimum feedback arc set problem and is one of Karp's 21 NP-complete problems