Say a I have a particular undirected graph. I'd like to transform it into a directed acyclic graph with as many edges as possible by doing one of the following operations for each (undirected) edge:
- Turn the undirected edge into one directed edge in an arbitrary direction.
- Remove the undirected edge.
Putting it differently, I would like to know how to decide on the existence and direction of each undirected edge, so that the induced directed graph has no loops and has the maximum possible number of edges.
Pointers to the name of this problem, or some terms I could use to search, would already be awesome.
Perhaps the answer is too obvious, but I'm failing to see it.
Thanks!
Best Answer
Actually, you will never have to remove an edge. For example, if your graph has $n$ vertices, you can number the vertices from $1$ to $n$ and then orient each edge to point to its higher numbered endpoint. This results in a DAG.