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


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.