An Algorithm for the Vertex Packing Problem

This paper presents several properties of the vertex packing problem and develops an algorithm for its solution. We show a relationship between the vertex packing problem on the original graph and on a class of related bipartite graphs. This can be used to generate good initial solutions, which in some cases are known to be optimal. We also show that the group-theoretic approach to integer programming, when applied to vertex packing, yields a trivial group problem regardless of the determinant of the associated basis matrix. These ideas are incorporated into an algorithm and computational experience is presented.