  In this work, we provide the first practical evaluation of the structural
rounding framework for approximation algorithms. Structural rounding works by
first editing to a well-structured class, efficiently solving the edited
instance, and "lifting" the partial solution to recover an approximation on the
input. We focus on the well-studied Vertex Cover problem, and edit to the class
of bipartite graphs (where Vertex Cover has an exact polynomial time
algorithm). In addition to the naive lifting strategy for Vertex Cover
described by Demaine et al., we introduce a suite of new lifting strategies and
measure their effectiveness on a large corpus of synthetic graphs. We find that
in this setting, structural rounding significantly outperforms standard
2-approximations. Further, simpler lifting strategies are extremely competitive
with the more sophisticated approaches. The implementations are available as an
open-source Python package, and all experiments are replicable.
