Partial Independent Dominant with Obligations in Graph,
Graph Study - Student Project

The problem of independent dominant sets with obligations is a variant of the classical problem of minimum independent dominant sets.
Let G be an undirected graph, and O, called the set of obligations, be a stable partition of the set of vertices of G. We want to know if there exists an independent dominant set E (i.e., every vertex of G is included in E or is adjacent to at least one vertex of E) respecting the obligations (i.e., if a vertex is included in E, all vertices of its obligation are also included). This problem is NP-complete.
This project was carried out in pairs, under the supervision of C. Laforest, as part of the final project of prep'isima II.
The idea was to propose partial resolution algorithms and evaluate them by generating instances and creating tools for evaluation and statistical visualization.