Fair Vertex Problems Parameterized by Cluster Vertex Deletion

1. Définition du problème et contexte

Problèmes de sommets équitables (Fair Vertex Problems) :
L'article examine des variantes « équitables » de problèmes classiques sur les graphes. Contrairement aux problèmes traditionnels qui cherchent un ensemble de solutions $X$ de cardinalité (taille) minimale, les problèmes équitables cherchent un ensemble $X$ minimisant le coût équitable.

• Coût équitable ($fc$) : Défini par $fc(X) := \max_{v \in V(G)} |N(v) \cap X|$.
• Objectif : Trouver un ensemble $X$ satisfaisant une propriété logique spécifique (par exemple, $G \setminus X$ est une forêt) tel qu'aucun sommet du graphe n'ait plus de $k$ voisins dans $X$.

Paramétrisation :
L'étude se concentre sur la paramétrisation structurelle par le nombre de Cluster Vertex Deletion (CVD).

• Nombre CVD : La taille du plus petit ensemble $D \subseteq V(G)$ (appelé modulateur) tel que $G \setminus D$ soit une collection de cliques disjointes.
• Contexte : Des travaux antérieurs ont établi que les problèmes Fair MSO$_1$ sont traitables en temps fixe (FPT) lorsqu'ils sont paramétrés par la Couverture de Jumeaux (Twin Cover), un paramètre plus fort. La question ouverte était de savoir si cela s'étendait au paramètre plus général Cluster Vertex Deletion.

Cadre logique :
Les problèmes sont définis à l'aide de la logique monadique du second ordre (MSO$_1$), qui permet la quantification sur les sommets et les ensembles de sommets (mais pas sur les arêtes). L'article considère deux variantes principales :

1. L-FairVD (Suppression) : Trouver $X$ tel que $G \setminus X \models \phi$.
2. L-FairVE (Évaluation) : Trouver des ensembles $W_1, \dots, W_\ell$ satisfaisant une formule $\phi(W_1, \dots, W_\ell)$.

---

2. Contributions clés

L'article fournit une dichotomie pour les problèmes Fair MSO$_1$ paramétrés par CVD :

1. Résultat de dureté (Négatif) :

   • Théorème 1 : Le problème Fair Vertex FO Deletion est W[1]-difficile lorsqu'il est paramétré par le nombre de suppression de sommets de cluster (pour CVD $>3$) et la taille de la formule.
   • Cela répond négativement à la question ouverte de [16], prouvant qu'un algorithme FPT général pour tous les problèmes Fair MSO$_1$ sous paramétrisation CVD est impossible (sauf si FPT = W[1]).

2. Résultat positif (Méta-théorème) :

   • Théorèmes 3 et 24 : Les auteurs identifient une condition suffisante sous laquelle les problèmes Fair MSO$_1$ sont FPT paramétrés par CVD.
   • La condition repose sur le concept de formes $\alpha$-cohérentes. Si un problème admet une solution où l'interaction entre l'ensemble de solutions et les cliques de $G \setminus D$ suit un motif « cohérent » spécifique (soit en sélectionnant presque tous les sommets, soit presque aucun, à partir de types de voisinage spécifiques au sein des cliques), un algorithme FPT existe.

3. Application algorithmique :

   • Le méta-théorème est appliqué pour résoudre plusieurs problèmes naturels en temps FPT, notamment :
     • Couverture de sommets équitable (Fair Vertex Cover)
     • Ensemble de sommets de rétroaction équitable (Fair Feedback Vertex Set)
     • Transversal de cycles impairs équitable (Fair Odd Cycle Transversal)
     • Ensemble dominant équitable (Fair Dominating Set)
     • Domination équitable $[\sigma, \rho]$ (pour $\sigma$ fini, ou $\sigma, \rho$ cofinis).

---

3. Méthodologie

Les auteurs emploient une combinaison sophistiquée de techniques de vérification de modèles, de théorie structurelle des graphes et de Programmation Linéaire en Nombres Entiers (PLNE).

A. Décomposition structurelle et « Formes »

Le cœur de l'algorithme repose sur la compression de l'espace des solutions à l'aide de Formes.

• Modulateur ($D$) : Le graphe est divisé en le modulateur $D$ et une collection de cliques $\mathcal{C}$ dans $G \setminus D$.
• Types de cliques : Les sommets d'une clique $C$ sont catégorisés par leur voisinage dans $D$. Un Type de clique est un vecteur comptant combien de sommets dans $C$ se connectent à chaque sous-ensemble de $D$.
• Motifs de solution : Pour une clique $C$, la solution $X$ est décrite par le nombre de sommets qu'elle sélectionne pour chaque type de voisinage.
• Formes : Une « Forme » est une représentation compacte (une matrice) qui agrège les comptes des cliques de types spécifiques et les motifs de solution qu'elles suivent.
  • Bornitude : Le nombre de sommets sélectionnés à partir d'un type de voisinage spécifique est plafonné à un seuil $\alpha$. Si le compte dépasse $\alpha$, il est traité comme « non borné » mais catégorisé soit comme mince (peu sélectionnés) soit comme épais (peu exclus).
  • Cohérence : Une forme est $\alpha$-cohérente si, pour chaque type de voisinage non borné, la solution est constamment « mince » (sélectionnant peu) ou « épaisse » (sélectionnant la plupart) à travers toutes les cliques de ce type.

B. Vérification de modèles sur les formes

• Sommets/Cliques non pertinents : En utilisant des outils logiques (spécifiquement le lemme du « sommet non pertinent » et le lemme de la « clique non pertinente »), les auteurs prouvent que si un graphe possède de nombreuses cliques du même type, la vérité d'une formule MSO$_1$ dépend uniquement de la forme de la solution, et non du nombre exact de cliques (à condition que ce nombre soit suffisamment grand).
• Lemme 13 : Établit que pour $\alpha$ et $\gamma$ suffisamment grands, $G \models \phi(X)$ si et seulement si la forme de $(G, X)$ satisfait la formule. Cela permet à l'algorithme de vérifier la condition logique sur la forme compressée plutôt que sur le graphe complet.

C. Programmation Linéaire en Nombres Entiers (PLNE)

Une fois une forme valide (satisfaisant la formule logique) identifiée, l'algorithme doit reconstruire une solution avec un coût équitable minimal.

• Formulation PLNE : Le problème de trouver un ensemble $X$ correspondant à une forme spécifique avec un coût équitable $\le k$ est formulé comme un PLNE.
  • Variables : Représentent le nombre de cliques d'un certain type assignées à un motif de solution spécifique.
  • Contraintes :
    1. Cohérence : Le nombre de cliques assignées doit correspondre aux comptes dans la matrice de forme.
    2. Coût équitable : Le nombre total de voisins dans $X$ pour n'importe quel sommet du modulateur $D$ ne doit pas dépasser $k$.
• Complexité : Le nombre de variables dans le PLNE dépend uniquement des paramètres (taille de la formule, nombre CVD, $\alpha$, $\gamma$), et non de la taille du graphe.
• Résolution : Le PLNE est résolu en utilisant l'algorithme de Lenstra (amélioré par Reis et Rothvoss), qui s'exécute en temps $f(p) \cdot \text{poly}(n)$, où $p$ est le nombre de variables. Cela garantit que l'algorithme global est FPT.

---

4. Preuve de dureté (W[1]-difficulté)

Pour prouver que le cas général est W[1]-difficile, les auteurs réduisent le problème depuis le Bin Packing $\ell$ unaire (connu pour être W[1]-difficile paramétré par $\ell$).

1. Réduction : Ils construisent un graphe où la taille du modulateur correspond au nombre de bacs ($d = \ell$).
2. Cliques comme objets : Chaque objet de l'instance de bin packing est représenté par une clique. La taille de la clique et ses connexions au modulateur encodent la taille de l'objet.
3. Logique : Une formule FO est construite pour imposer que, pour chaque clique, la solution doit « supprimer » un sous-ensemble spécifique de sommets correspondant à l'objet étant placé dans un bac spécifique.
4. Coût équitable : La contrainte de coût équitable assure que la capacité des bacs n'est pas dépassée.
5. Résultat : Une solution au problème Fair Vertex FO Deletion existe si et seulement si l'instance de Bin Packing est soluble. Puisque Bin Packing est W[1]-difficile, le problème Fair Vertex général sous CVD l'est également.

---

5. Signification et impact

• Résolution de questions ouvertes : L'article résout définitivement la question de savoir si les problèmes Fair MSO$_1$ sont FPT sous paramétrisation CVD. Il montre que si le problème général est intraitable (W[1]-difficile), une grande et naturelle sous-classe de problèmes est traitable.
• Méta-théorème pour les problèmes équitables : Il fournit un puissant méta-théorème (Théorème 24) permettant aux chercheurs de déterminer si un problème équitable spécifique est FPT en vérifiant la « cohérence » de sa structure de solution sur les cliques.
• Pont entre logique et optimisation : Ce travail combine élégamment la vérification de modèles MSO (logique) avec l'optimisation combinatoire (PLNE) pour gérer les contraintes d'équité, qui sont notoirement difficiles à paramétrer.
• Voies futures : L'article met en lumière des questions ouvertes, telles que savoir si la tractabilité s'étend au paramètre Largeur Modulaire (un paramètre plus dense) et si tous les cas de domination équitable $[\sigma, \rho]$ sont FPT. Il soulève également la question de savoir si ces problèmes sont dans XP (polynomial pour paramètre fixe) lorsqu'ils sont paramétrés par la Largeur de Clique.

En résumé, cet article établit une frontière nuancée pour la complexité paramétrée des problèmes de graphes équitables, prouvant qu'aucun algorithme FPT universel n'est possible pour CVD, mais qu'un cadre robuste existe pour résoudre efficacement de nombreux problèmes fondamentaux.