Some combinatorial optimization problems in a conflict situation

When a complex system has to be protected against attacks, one is often led to identify the d most vital elements of the system. In a similar spirit when a player A has to choose an action between a collection of “optimal” actions, one may imagine that an opponent P may try to prevent A from making a good choice by destroying some elements of the system. This can be concretized in several ways. We shall concentrate for illustration purposes to the case where the system is represented by a graph G (in which every vertex has a positive weight); the possible actions of A are the maximum weight independent (or stable) subsets S of vertices in G. Let d be a fixed integer. The opponent P has two options. Either find a minimum subset T of vertices to remove from G which is such that T has in common with every S a subset of vertices with total weight at least d or find a minimum subset B of vertices to remove such that in G-B the maximum weight of an independent subset S has decreased by at least d. We shall discuss this model and related ones and present a solution procedure for a bipartite graph G. Complexity of related problems will be stated. This is joint work with C.Bentz (Univ. Paris-Sud, Orsay), M.C.Costa (ENSTA, Paris), C.Picouleau (CNAM,Paris), B.Ries (Univ . Dauphine, Paris).