A general framework for finding d-transversals in graphs

Grégoire Cotté, Marie-Christine Costa and Christophe Picouleau
2015
Type de publication :
Conférence sans actes
Conférence :
EURO (Glasgow)
Résumé :
Let P be an optimisation problem on a finite set of elements V, where an optimal solution of P is a subset of V. A d-transversal T is a subset of V such that the intersection between T and any optimal solution of P contains at least d elements of V. A d-transversal is optimum when its size is minimum. Generally, the minimum transversal problem can be modelized as a bilevel 0-1 program which can be transformed in a 0-1 program with potentially an exponential number of constraints. We propose a general framework to solve this problem when P is modelized by a 0-1 mathematical program.We test the efficiency of this approach for the case where P is the maximum stable set or the maximum matching problem. In these cases, P can be modelized as a 0-1 linear program. Our algorithm is based on a constraints generation method and use a 0-1 linear program solver. We present numerical results for both problems.
BibTeX :
@conference{Cot-Cos-Pic-2015,
    author={Grégoire Cotté and Marie-Christine Costa and Christophe 
           Picouleau },
    title={A general framework for finding d-transversals in graphs },
    publisher={EURO (Glasgow) },
    year={2015 },
}