<figure><img src="image_1.png" /></figure>

HAL
open science

# Trouver un Indépendant Dominant respectant des Obligations dans les graphes

Timothée Martinod

► To cite this version:

Timothée Martinod. Trouver un Indépendant Dominant respectant des Obligations dans les graphes. Journées Nationales de l'Informatique Mathématique, Mar 2024, Grenoble (38000), France. hal-04505506

HAL Id: hal-04505506

https://hal.science/hal-04505506v1

Submitted on 15 Mar 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
## Contexte

Récemment, le concept de "conflit" a été introduit, exprimant l'interdiction d'utiliser simultanément deux éléments d'un système, souvent en raison d'une incompatibilité entre eux. Un conflit peut être une transition interdite dans un chemin [1].

La première apparition de la notion d'obligation remonte à [2]. Cette notion s'avère utile pour représenter des contextes où les éléments doivent être mobilisés de manière collective plutôt qu'individuelle (comme une équipe de personnes ou un ensemble de ressources) [3, 4].

## Indépendant Dominant : le problème de la couverture d'un réseau

Soit un graphe $G = (V, E)$. Un sous-ensemble solution $D$ au problème de l'indépendant dominant doit être :

* indépendant : il n'existe pas d'arête entre deux sommets de $D$ ($\forall v_1, v_2 \in D, v_1 v_2 \notin E$);

* dominant : tous les sommets de $G$ sont dans $D$ ou partagent une arête avec au moins l'un d'eux ($D \cup \mathcal{N}(D) = V$).

Un graphe contient toujours au moins un indépendant dominant.

<figure><img src="image_3.png" /></figure>

Soit $D = \{x_1, \dots, x_6\}$. $D$ est indépendant, aucune arête ne lie deux sommets $x_i$ entre eux. $D$ est dominant, chaque sommet $x_i$ y appartient et chaque sommet $c_i$ a au moins un voisin $x_i$. $D$ est une solution.

## Indépendant Dominant avec Obligations (IDO)

Soit un graphe $G = (V, E)$ et une partition de ses sommets $\Pi = \{\pi_1, \dots, \pi_I\}$ en obligations. Un sous-ensemble solution $D$ au problème de l'Indépendant Dominant avec Obligations doit :

* être une solution pour le problème de l'indépendant dominant;

* respecter les obligations : soit tous les sommets d'une obligation appartiennent à $D$ soit aucun ($\forall \pi_i \in \Pi, \pi_i \cap D \neq \emptyset \Rightarrow \pi_i \subseteq D$).

Un graphe peut ne contenir aucun indépendant dominant respectant les obligations.

<figure><img src="image_4.png" /></figure>

En respectant les obligations, seuls les sommets $x_4, x_5$ et $x_6$ peuvent appartenir à une solution sans violer la contrainte d'indépendance. Cependant ils ne permettent de dominer ni $c_1$ ni $x_1, x_2$ et $x_3$.

Ainsi, une solution ne peut contenir que des obligations stables.

Les quatre obligations ci-dessus contiennent chacune trois sommets, elles sont dites **3-équilibrées**.

**Objectif** : Déterminer si une instance admet un sous-ensemble de sommets indépendants, dominants et respectant les obligations pour une topologie de graphe donnée et des propriétés sur les obligations.

## Résultats de complexité

Le problème de l'IDO est $\mathcal{NP}$-complet dans les chemins et les graphes de diamètres **3** (topologies très simples) même avec des obligations stables et $\lambda \ge 2$-équilibrées.

Même en relâchant la contrainte de domination de tous les sommets, pour n'en dominer qu'un nombre cible, le problème demeure difficile.

Déterminer l'existence d'un sous-ensemble de sommets indépendants dominant au moins $3\sqrt{|V|} - 2$ sommets dans une collection de chemins et respectant les obligations stables est un problème $\mathcal{NP}$-complet.

Cependant, il est toujours possible de dominer au moins $2\sqrt{|V|} - 1$ sommets à condition d'avoir suffisamment d'obligations stables.

## Indépendant Dominant avec Obligations faibles (IDOf)

Bien que partant d'un problème trivial, déterminer l'existence d'un indépendant dominant respectant les obligations est un problème $\mathcal{NPC}$, même dans des conditions très restrictives.

Atténuons la contrainte que représentent les obligations.

Soit un graphe $G = (V, E)$, une partition de ses sommets $\Pi = \{\pi_1, \dots, \pi_I\}$ en obligations et un seuil $\kappa \ge 0$. Un sous-ensemble solution $D$ au problème de l'Indépendant Dominant avec Obligations doit :

* être une solution pour le problème de l'indépendant dominant;

* respecter les obligations : soit tous les sommets d'une obligation appartiennent à $D$ soit au plus $\kappa (\forall \pi_i \in \Pi, |\pi_i \cap D| > \kappa \Rightarrow \pi_i \subseteq D)$.

Un graphe peut ne contenir aucun indépendant dominant respectant les obligations faibles.

<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /></figure>

Une instance du problème IDOf peut représenter un triplet du problème RX3C.

<figure><img src="image_7.png" /></figure>

Il existe des connecteurs neutres pour relier plusieurs composantes connexes.

<figure><img src="image_8.png" /></figure>

**Objectif** : Déterminer si une instance admet un sous-ensemble de sommets indépendants, dominants et respectant les obligations faibles pour une topologie de graphe donnée et des propriétés sur les obligations.

## Résultats de complexité

Le problème de l'IDO est $\mathcal{NP}$-complet :

* s'il reste des obligations fortes stables, même si le graphe est un chemin, est dense ou a un faible diamètre;

* même dans un arbre ou une collection de chemins avec des obligations stables et équilibrées;

* même pour dominer relativement peu de sommets (ratio de $\kappa/\lambda$);

* sauf pour dominer $2\sqrt{|V|} - 1$ sommets + un coefficient de $\kappa$ avec des obligations stables.

## References

[1] Mamadou Moustapha Kanté, Christian Laforest, and Benjamin Momège. An exact algorithm to check the existence of (elementary) paths and a generalisation of the cut problem in graphs with forbidden transitions. In *SOFSEM 2013 Proceedings*, volume 7741 of *Lecture Notes in Computer Science*, pages 257–267. Springer, 2013.

[2] Alexis Cornet and Christian Laforest. Graph problems with obligations. In *Combinatorial Optimization and Applications*, volume (LNCS) 11346, pages 183–197, Cham, 2018. Springer International Publishing.

[3] Christian Laforest and Timothée Martinod. On the complexity of independent dominating set with obligations in graphs. *Theoretical Computer Science*, 904:1–14, 2022.

[4] Christian Laforest and Timothée Martinod. Introduction to routing problems with mandatory transitions. In *SOFSEM 2023 : Theory and Practice of Computer Science*, pages 254–266, Cham, 2023. Springer International Publishing.