0
$\begingroup$

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:

  1. Turn the undirected edge into one directed edge in an arbitrary direction.
  2. 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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks! I just realized I missed an important requirement in my problem formulation. Will create another post. $\endgroup$ – mvc May 17 at 20:21

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.