On the maximum weighted irredundant set problem

KATZ, RICARDO D.; DANIEL SEVERÍN

REVISTA DE LA UNIóN MATEMáTICA ARGENTINA

UNION MATEMATICA ARGENTINA

Lugar: Bahia Blanca; Año: 2023

0041-6932

We present a generalization of a well-known domination parameter, the  upper irredundance number, and address its associated optimization problem, namely the Maximum Weighted Irredundant Set (MWIS) problem, which models some service allocation problems. We establish a polynomial time reduction to the Maximum Weighted Stable Set (MWSS) problem that we use to find graph classes for which the MWIS problem is polynomial, among other results. We formalize these results in the proof assistant Coq. This is mainly convenient in the case of some of them due to the structure of their proofs. We also present a heuristic and an integer programming formulation for the MWIS problem and check that the heuristic delivers good quality solutions through experimentation.