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.