d-Transversals of stable sets and vertex covers in weighted bipartite graphs

Bentz, Cédric; Costa, Marie-Christine; Picouleau, Christophe; Ries, Bernard; de Werra, Dominique

Bentz, Cédric; Costa, Marie-Christine; Picouleau, Christophe; Ries, Bernard; de Werra, Dominique (2012), d-Transversals of stable sets and vertex covers in weighted bipartite graphs, Journal of Discrete Algorithms, 17, p. 95-102. http://dx.doi.org/10.1016/j.jda.2012.06.002

Type

Article accepté pour publication ou publié

Date

2012

Journal name

Journal of Discrete Algorithms

Volume

Publisher

Elsevier

Pages

95-102

Abstract (EN)

Let G=(V,E) be a graph in which every vertex v∈V has a weight w(v)⩾0 and a cost c(v)⩾0. Let SG be the family of all maximum-weight stable sets in G. For any integer d⩾0, a minimum d-transversal in the graph G with respect to SG is a subset of vertices T⊆V of minimum total cost such that |T∩S|⩾d for every S∈SG. In this paper, we present a polynomial-time algorithm to determine minimum d-transversals in bipartite graphs. Our algorithm is based on a characterization of maximum-weight stable sets in bipartite graphs. We also derive results on minimum d-transversals of minimum-weight vertex covers in weighted bipartite graphs.

Subjects / Keywords

Transversal; Matching; Stable set; Vertex cover; Bipartite graph; Network flow