An extension of the könig-egerváry property to node-weighted bidirected graphs

Given a bidirected graphG and a vectorb of positive integral node-weights, an integer linear program IP is defined on (G, b). IP generalizes the node packing problem on a node-weighted (undirected) graph in the sense that it reduces to the latter whenG is undirected. A polynomial time algorithm is given that recognizes whether CP (the linear program obtained by relaxing the integrality constraints of IP) has an integral optimal solution. Also an efficient method for solving the linear programming dual of CP is described.Supported by the Natural Sciences and Engineering Research Council of Canada.