Weighted Transversals and Blockers for Some Optimization Problems in Graphs

A general formulation of the problems we are going to consider may be sketched as follows: we are given a system S which is operated by an actor A; this actor tries to choose among several optimal actions which may be represented by subsets of S.An opponent O wants to prevent actor A from operating S in an optimum way by destroying some part P of S. O may in particular wish to find a part P of S as small as possible whose removal will reduce the efficiency of the operation of the system S by a given amount. Another way for O would be to determine a smallest possible part P (the most vital elements) which hits in a sufficient amount every possible optimal action of A.This kind of problem occurs in various situation related to safety or reliability or even in game theoretic contexts.Such problems have been studied from a theoretical point of view in very special cases for which combinatorial optimization models may give an acceptable represen- tation of S. It leads to challenging optimization problems; the goal of this chapter is to give a partial survey of such situations while focusing on simple models based on graphs and other (hopefully tractable) combinatorial structures