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 < v_2 < \dots < v_n$ such that minimizes $\vert F \vert$, where $F = \{ \langle v_i,v_j \rangle \ \vert\ v_i < 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 < a < 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 < b < a$, because $b < a$ and $c < 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 :)
