A LINEAR PROGRAMMING RELAXATION OF THE NODE PACKING PROBLEM OR 2-BICRITICALGRAPHS AND NODE COVERS
Abstract
The problem of finding a minimum cardinality set of nodes
in a graph which meet every edge is of considerable theoretical as well as
practical interest. Because of the difficulty of this problem, a linear
relaxation of an integer programming model is sometimes used as a
heuristic. In fact Nemhauser and Trotter showed that any variables
which receive integer values in an optimal solution to the relaxation
can retain the same values in an optimal solution to the integer
program.
We define 2-bicritical graphs and give several characterizations of
them.
One characterization is that they are precisely the graphs for which
an optimal solution to the linear relaxation will have no integer
valued variables. Then we show that almost all graphs are 2-bicritical,
and hence the linear relaxation almost never helps.
Description
Keywords
Computer Science