Irrégularité de Graphe via Suppression d'Arêtes

Informations Fondamentales

• ID de l'article : 2511.14514
• Titre : Graph Irregularity via Edge Deletions
• Auteurs : Julien Bensmail, Noémie Catherinot, Foivos Fioravantes, Clara Marcille, Nacim Oijid
• Classification : math.CO (mathématiques combinatoires), cs.CC (complexité computationnelle), cs.DM (mathématiques discrètes)
• Date de publication : 18 novembre 2025 (prépublication arXiv)
• Lien de l'article : https://arxiv.org/abs/2511.14514

Résumé

Cet article étudie le problème de l'irrégularité de graphe par suppression d'arêtes, paramétré par Ie(G), qui représente le nombre minimum k d'arêtes à supprimer pour rendre un graphe G localement irrégulier (deux sommets adjacents quelconques ont des degrés différents). Bien que ce problème soit prouvé NP-difficile et W1-difficile, les auteurs proposent deux algorithmes FPT : l'un concernant la taille de la solution plus le degré maximum ∆, l'autre concernant le nombre de couverture de sommets. De plus, les auteurs étudient en profondeur les graphes denses, en particulier les graphes complets, et proposent une conjecture importante : pour tout graphe connexe G, Ie(G) ≤ m/3 + c, où m est le nombre d'arêtes et c est une constante. Cette conjecture est vérifiée sur plusieurs classes de graphes, y compris les arbres.

Contexte et Motivation de la Recherche

Définition du Problème

En théorie des graphes, les graphes réguliers représentent les graphes où tous les sommets ont le même degré. Comme concept dual, les chercheurs ont proposé plusieurs définitions d'irrégularité :

1. Graphes irréguliers : tous les degrés des sommets sont distincts deux à deux
2. Graphes hautement irréguliers : les degrés des voisins de chaque sommet sont tous différents
3. Graphes localement irréguliers : deux sommets adjacents quelconques ont des degrés différents

Cet article se concentre sur le concept de graphes localement irréguliers.

Importance de la Recherche

1. Signification théorique : l'irrégularité locale est une propriété structurelle importante en théorie des graphes, étroitement liée à la célèbre conjecture 1-2-3
2. Perspective opérationnelle : les recherches antérieures se concentraient principalement sur l'ajout d'arêtes (comme la multiplicité des arêtes) pour réaliser l'irrégularité, tandis que cet article explore l'opération plus restrictive de suppression d'arêtes
3. Complexité paramétrée : ce problème présente une hiérarchie riche de complexité computationnelle, appropriée pour la recherche en algorithmes paramétrés

Limitations des Méthodes Existantes

• Fioravantes et al. 10 ont récemment introduit le concept de sous-ensemble d'irrégularité d'arête, prouvant que le calcul du sous-ensemble d'irrégularité d'arête optimal est NP-difficile
• Ce problème est W1-difficile concernant la taille de la solution et l'ensemble de sommets de rétroaction
• Le comportement pour les graphes denses (comme les graphes complets) et certains paramètres structurels (diversité de voisinage, distance à une clique) reste peu clair

Motivation de la Recherche

Les auteurs visent à :

1. Concevoir des algorithmes FPT efficaces pour des paramètres spécifiques
2. Comprendre les valeurs exactes ou les bornes supérieures de Ie(G) pour différentes classes de graphes
3. Explorer la relation universelle entre Ie(G) et le nombre d'arêtes m du graphe

Contributions Principales

1. Algorithmes paramétrés :
   • Proposition d'un algorithme FPT concernant la taille de la solution k plus le degré maximum ∆, avec une taille de noyau de O(k∆^(2k+2))
   • Proposition d'un algorithme FPT concernant le nombre de couverture de sommets vc, avec une complexité temporelle de 2^O(vc^4)·n^O(1), supérieur aux méthodes précédentes basées sur la programmation linéaire en nombres entiers
2. Résultats structurels :
   • Preuve de formules exactes pour les chemins et les cycles
   • Preuve pour les graphes bipartis complets Kn,m : Ie = 0 quand n≠m, Ie = n quand n=m
   • Preuve pour les arbres T : Ie(T) ≤ |E(T)|/3 (sauf si T est un chemin)
   • Pour les graphes complets d'ordre tk (nombre triangulaire), formule exacte : Ie(Ktk) = |E(Ktk)| - k(k+1)(k-1)(3k+2)/24
3. Conjecture importante (Conjecture 1) : Il existe une constante c telle que pour tout graphe connexe G avec m arêtes, Ie(G) ≤ m/3 + c
4. Perspectives théoriques :
   • Fourniture d'une borne inférieure générale pour Ie(G) : Ie(G) ≥ ⌈conf(G)/(2∆-1)⌉
   • Preuve que les arêtes du sous-ensemble d'irrégularité d'arête optimal doivent être proches des arêtes de conflit (Lemme 1)

Explication Détaillée des Méthodes

Définition de la Tâche

Entrée : graphe G = (V, E) et entier positif k ≥ 1
Sortie : déterminer si Ie(G) ≤ k (version décisionnelle) ou calculer le sous-ensemble d'irrégularité d'arête optimal (version optimisation)

Définitions :

• Un graphe G est localement irrégulier si pour toute arête uv ∈ E, on a dG(u) ≠ dG(v)
• Sous-ensemble d'irrégularité d'arête : ensemble d'arêtes S ⊆ E tel que G-S est localement irrégulier
• Ie(G) : taille du sous-ensemble d'irrégularité d'arête minimal
• conf(G) : nombre de conflits, c'est-à-dire le nombre d'arêtes uv satisfaisant dG(u) = dG(v)

Méthodes Techniques Fondamentales

1. Algorithme de Noyautage concernant k+∆ (Théorème 2)

Lemme clé 1 : Soit S un sous-ensemble d'irrégularité d'arête optimal de G, alors toute arête e ∈ S est à distance au plus 2|S|-1 d'une arête de conflit.

Esquisse de preuve (par induction) :

• Base : pour k=1, l'unique arête supprimée doit être adjacente à un conflit
• Induction : pour k≥2, pour tout conflit uv, il existe e∈S adjacent à u ou v ; appliquer l'hypothèse d'induction dans G-{e}

Règles de noyautage :

1. Si conf(G) ≥ k(2∆+1), retourner une instance négative
2. Pour chaque arête de conflit e, définir la boule B(e, 2k+1) contenant tous les sommets à distance au plus 2k+1 des extrémités de e
3. Construire le sous-graphe H = G∪e∈EC Ve, où Ve est la boule de e
4. Ajuster les degrés des sommets dans H pour correspondre à G (en ajoutant des feuilles)

Analyse de la taille du noyau :

• Nombre de conflits |EC| ≤ k(2∆+1)
• Chaque boule contient au plus 2∆^(2k) sommets
• Nombre total de sommets : |V(H)| ≤ 2k(2∆+1)∆^(2k+1) = O(k∆^(2k+2))

2. Algorithme concernant le Nombre de Couverture de Sommets (Théorème 5)

Cadre algorithmique :

1. Soit C = {u1,...,uvc} une couverture de sommets minimale, I = V\C l'ensemble indépendant
2. Partitionner I en I1 et I2 :
   • I1 : sommets de l'ensemble indépendant adjacents à un sommet de C de degré ≤ 5vc
   • I2 : autres sommets de l'ensemble indépendant
3. Définir G1 = GC∪I1, G2 = GC∪I2
4. Énumérer tous les S1 = S∩E(G1) possibles (au maximum 2^O(vc^4) variantes)
5. Pour chaque S1, calculer le minimum S2⊆E2 tel que G-(S1∪S2) soit localement irrégulier

Observation clé (Réclamation 7) : Pour tout sous-ensemble d'irrégularité d'arête optimal S cohérent avec S1, on a |S∩E2| ≤ vc^2

Technique d'optimisation (Réclamation 8) : Pour u∈C et v1,v2∈I2, si uv1∈S mais uv2∉S, on peut échanger pour obtenir une solution optimale équivalente. Par conséquent, il suffit de deviner pour chaque u∈C le nombre d'arêtes supprimées ki, satisfaisant Σki ≤ vc^2.

Complexité temporelle : 2^(vc+5vc^2)^2 · vc^(vc^2) · n^2 = 2^O(vc^4) · n^O(1)

Points d'Innovation Technique

1. Technique de limitation de distance : le Lemme 1 établit la relation spatiale entre les arêtes de la solution optimale et les conflits, ce qui est la clé du noyautage
2. Stratégie de préservation du degré : préserver les degrés en ajoutant des feuilles, garantissant l'équivalence entre le sous-problème et le problème original
3. Stratification d'ensemble indépendant : partitionner l'ensemble indépendant selon le degré des voisins, exploitant la structure bipartite du graphe
4. Lemme d'échange : prouver que les arêtes spécifiques supprimées vers l'ensemble indépendant ne sont pas importantes, seul le nombre de suppressions compte

Configuration Expérimentale

Cet article est une recherche théorique, basée principalement sur des preuves mathématiques plutôt que sur une vérification expérimentale. Cependant, une analyse constructive est menée sur plusieurs classes de graphes :

Classes de Graphes Étudiées

1. Chemins Pn et cycles Cn
2. Graphes bipartis complets Kn,m
3. Arbres
4. Graphes complets Kn (particulièrement les cas d'ordre nombre triangulaire)
5. Graphes bipartis connexes généraux
6. Graphes connexes généraux

Méthodes d'Analyse

• Dérivation de formules exactes : pour les chemins, les cycles, les graphes complets spécifiques
• Preuve de bornes supérieures : pour les arbres, les graphes bipartis, les graphes généraux
• Preuve constructive : démonstration de sous-ensembles d'irrégularité d'arête spécifiques atteignant les bornes
• Algorithme récursif : calcul exact en O(n∆^3) pour les arbres

Résultats Expérimentaux

Résultats Principaux

1. Chemins et Cycles (Théorème 9)

Pour les chemins Pn avec n≥2 :

• Ie(Pn) = (n-1)/3, quand n≡1 (mod 3)
• Ie(Pn) = ⌈(n-1)/3⌉, quand n≡2 (mod 3)
• Ie(Pn) = ⌊(n-1)/3⌋, sinon

Pour les cycles avec n≥3 : Ie(Cn) = Ie(Pn) + 1

Stratégie de preuve : partitionner le chemin en groupes consécutifs de trois arêtes, chaque groupe nécessitant la suppression d'au moins une arête

2. Graphes Bipartis Complets (Théorème 10)

• Ie(Kn,m) = 0, quand n≠m (déjà localement irrégulier)
• Ie(Kn,n) = n (suppression de toutes les arêtes d'un sommet)

3. Arbres (Théorème 13)

Théorème principal : pour tout arbre T, soit T est un chemin, soit Ie(T) ≤ |E(T)|/3

Esquisse de preuve :

• Pour les étoiles et les doubles étoiles, suppression des arêtes à distance 2 du centre
• Pour les arbres généraux, utilisation de l'induction, sélection du sommet de degré ≥3 le plus profond
• Analyse détaillée des cas (selon la structure des sous-arbres et les degrés)

Résultat algorithmique (Théorème 15) : calcul exact de Ie(G) pour les arbres en temps O(n∆^3)

4. Graphes Complets (Théorème 16)

Pour les graphes complets d'ordre n = tk = k(k+1)/2 (k-ième nombre triangulaire) :

Ie(Ktk) = |E(Ktk)| - mk

où mk = k(k+1)(k-1)(3k+2)/24

Construction : graphe localement irrégulier Tk de nombre maximal d'arêtes avec séquence de degrés : 1 sommet de degré n-1, 2 sommets de degré n-2, ..., k sommets de degré n-k

5. Bornes Supérieures pour les Graphes Généraux

Graphes bipartis (Théorème 11) : Pour les graphes bipartis connexes de degré minimum 1 : Ie(G) ≤ n-1

Graphes généraux (Théorème 12) : Pour tout graphe connexe : Ie(G) ≤ ⌊m/2⌋ + n + ∆ - 2

Vérification de la Conjecture

Conjecture 1 : il existe une constante c telle que pour tout graphe connexe G avec m arêtes, Ie(G) ≤ m/3 + c

Classes de graphes vérifiées :

• ✓ Cycles (c≥2)
• ✓ Arbres
• ✓ Graphes complets d'ordre nombre triangulaire
• ✓ Graphes bipartis complets
• ✓ Par le Théorème 12, les graphes généraux satisfont une borne plus faible

Serrage (Théorème 1) : Pour le graphe G obtenu en subdivisant deux fois chaque arête d'un graphe H : Ie(G) ≥ m/3 Par conséquent, le coefficient 1/3 est serré.

Perspectives Clés

1. Efficacité de résolution des conflits : la suppression d'une arête résout au maximum 2∆-1 conflits (Remarque 1)
2. Exigence de connexité : la connexité dans la Conjecture 1 est nécessaire (l'appariement parfait nécessite la suppression de toutes les arêtes)
3. Graphes creux vs denses : les graphes creux (comme les arbres) atteignent plus facilement la borne m/3, tandis que les graphes denses (comme les graphes complets) présentent un comportement complexe

Travaux Connexes

Spectre de Recherche sur l'Irrégularité de Graphe

1. Graphes irréguliers 6 : Chartrand et al. introduisent la force d'irrégularité (irregularity strength), réalisant l'irrégularité en augmentant la multiplicité des arêtes
2. Graphes hautement irréguliers 1,5 : Alavi et al. étudient les graphes où les degrés des voisins de chaque sommet sont tous différents
3. Graphes localement irréguliers 2,12 :
   • Karoński, Luczak, Thomason proposent la conjecture 1-2-3 (récemment résolue par Keusch 13)
   • Baudon et al. étudient la décomposition des graphes réguliers en sous-graphes localement irréguliers

Introduction de Propriétés via Opérations de Suppression

4. Introduction de régularité 3,4 :
   • Bazgan et al. réalisent l'anonymisation des degrés via rotation d'arêtes
   • Belmonte et Sau étudient la recherche de grands sous-graphes induits impairs
5. Sous-ensembles d'irrégularité de sommets 11 :
   • Fioravantes et al. introduisent la réalisation de l'irrégularité locale via suppression de sommets
   • Preuve d'algorithmes FPT concernant la largeur d'arbre et le degré maximum
6. Sous-ensembles d'irrégularité d'arête 10 :
   • Concept récemment introduit (prédécesseur direct de cet article)
   • Preuve de la NP-difficulté et de plusieurs résultats W1-difficiles

Contributions Uniques de Cet Article

Par rapport aux travaux connexes :

• Première proposition d'algorithmes FPT concernant k+∆ et le nombre de couverture de sommets
• Première étude systématique des valeurs exactes pour plusieurs classes de graphes
• Première proposition de la conjecture m/3+c et sa vérification extensive
• Étude approfondie des graphes complets, posant les fondations pour la compréhension des graphes denses

Conclusion et Discussion

Conclusions Principales

1. Niveau algorithmique : bien que le problème soit W1-difficile sous plusieurs paramètres, des algorithmes FPT peuvent être obtenus via des paramètres combinés (k+∆) ou des paramètres structurels (nombre de couverture de sommets)
2. Niveau structurel :
   • Ie(G) peut être déterminé exactement ou étroitement borné pour plusieurs classes de graphes
   • Le comportement des arbres et des graphes creux est relativement simple
   • Les graphes complets présentent une structure subtile liée aux nombres triangulaires
3. Niveau théorique : si la Conjecture 1 est vraie, elle unifiera la caractérisation du comportement asymptotique de Ie(G)

Limitations

1. Incomplétude pour les graphes complets : seul le cas d'ordre nombre triangulaire est résolu, la valeur exacte de Ie pour les graphes complets généraux Kn reste inconnue
2. Constante dans la Conjecture 1 : bien que vérifiée sur plusieurs classes de graphes, la valeur exacte de la constante c et la preuve générale restent manquantes
3. Efficacité algorithmique :
   • L'algorithme FPT pour k+∆ dépend exponentiellement de ∆^(2k), limitant les applications pratiques
   • L'algorithme de couverture de sommets, bien qu'amélioré par rapport aux méthodes ILP, conserve une dépendance 2^O(vc^4)
4. Paramètres pour graphes denses : la FPT-tractabilité concernant la diversité de voisinage et la distance à une clique reste non résolue

Directions Futures

Les directions explicitement proposées par les auteurs :

1. Paramètre de conflit dynamique : amélioration du paramètre conf statique pour capturer dynamiquement l'évolution des conflits
2. Graphes complets et cubiques :
   • Détermination de la valeur exacte de Ie pour les graphes complets généraux Kn
   • Resserrement des bornes pour les graphes cubiques
3. Extension aux graphes k-dégénérés : utilisation de techniques similaires pour obtenir une borne de (k-1)n + ⌊n/3⌋
4. Paramétrisation par largeur d'arbre : l'algorithme de version sommets de la littérature 11 devrait pouvoir s'adapter à la version arête
5. Diversité de voisinage : nécessite une résolution complète du problème des graphes complets avant traitement

Évaluation Approfondie

Points Forts

1. Profondeur théorique :
   • Techniques de preuve sophistiquées, particulièrement le Lemme 1 sur la limitation de distance et la preuve par induction pour les arbres
   • L'algorithme de noyautage démontre une compréhension profonde de la complexité paramétrée
   • Le résultat sur les nombres triangulaires pour les graphes complets révèle une structure combinatoire profonde
2. Systématicité :
   • Couverture de plusieurs classes de graphes, du creux au dense
   • Combinaison de résultats algorithmiques et structurels
   • Intégration de l'analyse théorique et des preuves constructives
3. Proposition de conjecture :
   • La Conjecture 1 possède une forte unité et un pouvoir heuristique
   • La vérification sur plusieurs classes de graphes renforce la crédibilité
   • Le Théorème 1 prouve le caractère serré du coefficient 1/3
4. Qualité de rédaction :
   • Structure claire, progression du simple au complexe
   • Preuves détaillées mais non redondantes
   • Illustrations d'appui à la compréhension (comme les Figures 3, 4)
5. Algorithmes pratiques :
   • L'algorithme O(n∆^3) pour les arbres possède une complexité polynomiale
   • Les algorithmes FPT fournissent des garanties théoriques pour les applications pratiques

Insuffisances

1. Lacunes de complétude :
   • Le cas général des graphes complets reste non résolu, limitant la compréhension des graphes denses
   • La Conjecture 1 manque de preuve générale
2. Praticité algorithmique :
   • La dépendance doublement exponentielle de l'algorithme k+∆ limite les applications pratiques
   • Absence d'évaluation expérimentale de la performance algorithmique
3. Optimisation des constantes :
   • La borne du Théorème 12 ⌊m/2⌋+n+∆-2 peut ne pas être serrée
   • Les valeurs exactes de la constante c pour diverses classes de graphes ne sont pas déterminées
4. Analyse des bornes inférieures :
   • Au-delà de conf(G)/(2∆-1), manque de techniques de borne inférieure plus raffinées
   • Pas de discussion sur les algorithmes d'approximation
5. Hiérarchie de paramètres :
   • Caractérisation incomplète de la frontière entre FPT et W1-difficile
   • Certains paramètres naturels (comme largeur d'arbre+∆) ne sont pas explorés

Impact

1. Contribution théorique :
   • Établissement de fondations solides pour la recherche sur les sous-ensembles d'irrégularité d'arête
   • Si la Conjecture 1 est vraie, ce sera un résultat combinatoire important
   • Les méthodes (particulièrement le Lemme 1) peuvent s'appliquer à d'autres problèmes de modification de graphe
2. Recherches ultérieures :
   • Le problème des graphes complets attirera l'attention des combinatoriciens
   • Les techniques d'algorithmes FPT peuvent se généraliser à d'autres propriétés locales
   • Offre une nouvelle perspective pour comprendre l'irrégularité locale des graphes
3. Valeur pratique :
   • L'algorithme pour les arbres peut s'appliquer directement à l'analyse de réseaux
   • Fournit un support théorique pour les applications telles que l'anonymisation de graphes et la robustesse de réseau
4. Ouverture :
   • Laisse des problèmes ouverts clairs et attrayants
   • Différents niveaux de difficulté conviennent à différents chercheurs

Scénarios d'Application

1. Conception de réseaux : scénarios où les nœuds adjacents ne doivent pas avoir le même degré (comme l'équilibrage de charge)
2. Anonymisation de graphes : suppression d'arêtes pour briser les motifs de degrés, protégeant la vie privée
3. Informatique théorique :
   • Cas d'étude en enseignement de la complexité paramétrée
   • Paradigme de recherche pour les problèmes de modification de graphe
4. Optimisation combinatoire : comme sous-problème de problèmes d'optimisation plus complexes

Références Clés

2 Baudon et al. (2015) : décomposition des graphes réguliers en sous-graphes localement irréguliers
6 Chartrand et al. (1988) : réseaux irréguliers, introduction de la force d'irrégularité
10 Fioravantes et al. (2024) : introduction des sous-ensembles d'irrégularité d'arête, preuve des résultats de difficulté fondamentale
11 Fioravantes et al. (2025) : complexité des sous-ensembles d'irrégularité de sommets
12 Karoński et al. (2004) : conjecture 1-2-3
13 Keusch (2024) : résolution de la conjecture 1-2-3

Évaluation Globale : Ceci est un article de haute qualité en informatique théorique, apportant des contributions substantielles à l'intersection de la complexité paramétrée et de la théorie des graphes. Bien que certains problèmes (particulièrement les graphes complets) ne soient pas complètement résolus, l'article fait progresser systématiquement la compréhension des sous-ensembles d'irrégularité d'arête, et la conjecture proposée possède une importance théorique significative. Les méthodes sont novatrices, les preuves rigoureuses, et les directions futures sont clairement établies. Recommandation de publication dans une revue de premier plan en mathématiques combinatoires ou en informatique théorique.