[CCP15a] A general framework for finding d-transversals in graphs

Conférence Internationale avec comité de lecture : EURO, July 2015, pp.1, Glasgow, United Kingdom,
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.


@inproceedings {
title="{A general framework for finding d-transversals in graphs}",
author=" G. Cotté and M.-C. Costa and C. Picouleau ",
address="Glasgow, United Kingdom",