HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
problemtheordergraphoptimaledgeslaterwellknownminimizes

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

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

Solution

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

Context

StackExchange Computer Science Q#68894, answer score: 3

Revisions (0)

No revisions yet.