In this paper, we derive lower bounds on the size of a minimum cover of a graph G by computing packings of edges, odd cycles and cliques of G of size 4. These bounds are embedded in a branch-and-bound algorithm for the maximum clique and stable set problems, called FLORA, that is competitive with a previously reported quadratic 0–1 optimization algorithm called SQUEEZE. We also indicate how this bounding approach can be generalized to computing packings of edges and subgraphs of G that induce valid inequalities for the node covering problem. Our bounding procedure is akin to the column generation method for solving linear programs in which the number of variables is huge.
