Minimum d-blockers and d-transversals in graphs

Marie-Christine Costa, Dominique de Werra and Christophe Picouleau
Publication type:
Paper in peer-reviewed journals
Journal of Combinatorial Optimization, vol. 22-4, pp. 857-872
Keywords :
transversal, blocker, cover, bipartite graph, matching, s. t path, s . t cut, stable set, bilevel programming.
We consider a set V of elements and an optimization problem on V : the search for a maximum (or minimum) cardinality subset of V verifying a given property P. A d-transversal is a subset of V which intersects any optimum solution in at least d elements while a d-blocker is a subset of V whose removal deteriorates the value of an optimum solution by at least d. We present some general characteristics of these problems, we review some situations which have been studied (matchings, s . t paths and s . t cuts in graphs) and we study d-transversals and d-blockers for new problems as stable sets or vertex covers in bipartite graphs.
    author={Marie-Christine Costa and Dominique de Werra and Christophe 
           Picouleau },
    title={Minimum d-blockers and d-transversals in graphs },
    doi={10.1007/s10878-010-9334-6 },
    journal={Journal of Combinatorial Optimization },
    year={2011 },
    volume={22-4 },