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