# Mengxue Yang

## Contact

Email: myang59@uic.edu
Office: SEO 731
Department website: Mengxue Yang

I learned the following fun piece of math from teaching the Young Scholar Program at UIC recently. The minimum vertex cover problem asks: for a given graph, find a minimal set of vertices that touch all the edges. This is one of Karp's 21 NP-complete problems. We can find a simple algorithm that outputs a good-enough approximate solution, but it's not what you think it is. The naive greedy algorithm is to always add a vertex of the highest degree to the vertex cover, then remove it from the graph and recurse. However there are graphs on which this algorithm produces vertex covers that are arbitrarily far from the minimal one. That is, $n$ times the size of a minimal cover, for any $n$.