From a directed graph (A), produce an undirected graph (B) with an edge for at least one outgoing edge for every vertex in A, minimizing edges

Question

Problem: Given a directed graph $A$, produce an undirected graph $B$ with the same vertices and minimum number of edges satisfying the following constraint:

• For each vertex in $A$, at least one outgoing edge must be replaced by an undirected edge in $B$. If an edge in $A$ is bidirectional, then it can be replaced by a single edge in $B$.

The worst case is randomly creating one edge in $B$ for a random outgoing edge for every vertex in $A$. This would yield $|V|$ edges. However, the constraint allows for optimization by replacing bidirectional edges with a single undirected edge in $B$, resulting in as low as $|V|/2$ edges. However, if a vertex in $A$ already has an outgoing connection replaced in $B$ then replacing another bidirectional edge is not optimal. This mutual exclusion causes a need to examine the optimal way to pair vertices.

Source: Interestingly, this problem comes from trying to fix cases the Mark Bayazit algorithm fails for convex decomposition. Reflex points are given a range. Any line within the range will resolve the reflex point and thus increase how convex the shape is. Connecting two reflex points which have each other in their ranges is most optimal: it eliminates two reflex points with a single line. However, simply connecting reflex points leads to constrained choices down the road. You can find the full Algorithm here: https://mpen.ca/406/bayazit

Answer 1

Thinking more about it, I may have found a solution. Temporarily simplifying the representation led me to some algorithms on Google, and the remainder is trivial.

If we create an undirected graph $C$ which has an edge for every bidirectional edge in $A$, then we need to find a "Maximum Matching" of the graph. I found some algorithms to do this at iq.opengenus.org.

Let us include all edges of a maximum matching in $B$. Next, for each vertex in $A$ which does not have any outgoing edge created in $B$, pick a random outgoing edge and create it in $B$.

Now, to actually solve the cases the Mark Bayazit algorithm fails, additional issues like if the resulting edges intersect need to be evaluated as well, so I wont be choosing randomly in my implementation.