3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

Szymon Stankiewicz is right -- this problem is basically Feedback Arc Set, which is unfortunately NP-complete. But I have to mention that a very similar graph property, which goes by the slightly alarming name of agony, can actually be computed in just $O(m^2)$ time, where $m$ is the number of edges. The agony of a graph is essentially a weighted form of the size of the feedback arc set, in which we weight each violated arc by "how much" it is violated. Specifically, if we group the vertices into horizontal levels so that every downward edge has a penalty of 0 and every horizontal or upward edge has a penalty equal to one more than the number of levels crossed, the agony is the minimum possible penalty that could be produced by any such grouping.

See http://users.ics.aalto.fi/ntatti/papers/tatti14agony.pdf for the $O(m^2)$ algorithm, due to Nikolaj Tatti, which will construct an agony-minimising hierarchy. (Note that I myself have only read the abstract and enough to confirm that an actual hierarchy will be produced, not just the minimal agony score of one).

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

Layered graph drawing

Layered graph drawing is a graph in which the vertices of a directed graph are drawn in horizontal rows or layers with the edges generally directed downwards. . However, graphs often contain cycles, minimizing the number of inconsistently-oriented edges is NP-hard, and minimizing the number of crossings is also NP-hard. enter image description here

source: wikipedia : Layered Graph Drawing

your problem is strikingly similar to the problem of minimizing number of crossings:

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.