Is the optimal order of graph vertices s.t. minimizes edges to later vertices a well-known problem?

cs.stackexchange https://cs.stackexchange.com/questions/68894

  •  04-11-2019
  •  | 
  •  

質問

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:

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 :)

正しい解決策はありません

ライセンス: CC-BY-SA帰属
所属していません cs.stackexchange
scroll top