Une approche CSP aux Problèmes de Sandwich de Graphes

Informations Fondamentales

• ID de l'article: 2510.09128
• Titre: A CSP approach to Graph Sandwich Problems
• Auteurs: Manuel Bodirsky, Santiago Guzmán-Pro (TU Dresden)
• Classification: cs.DM (Mathématiques Discrètes), cs.CC (Complexité Computationnelle), math.CO (Combinatoire)
• Date de publication: 13 octobre 2025
• Lien de l'article: https://arxiv.org/abs/2510.09128

Résumé

Le problème de sandwich de graphes (Graph Sandwich Problem, SP) est un problème computationnel important en théorie des graphes. Pour une classe de graphes $\mathcal{C}$, son problème de sandwich est défini comme suit : étant donnés deux graphes $(V,E_1)$ et $(V,E_2)$ avec $E_1 \subseteq E_2$, déterminer s'il existe un ensemble d'arêtes $E$ tel que $E_1 \subseteq E \subseteq E_2$ et le graphe $(V,E)$ appartient à $\mathcal{C}$. Cet article démontre que de nombreux problèmes de sandwich sont équivalents aux problèmes de satisfaction de contraintes (CSP) de graphes infinis à 2-coloration d'arêtes $H$, et utilise la théorie CSP pour fournir de nouveaux résultats de complexité pour plusieurs classes de graphes, notamment les graphes de lignes de multigraphes, les graphes de lignes de multigraphes bipartis, les graphes parfaits $K_k$-libres, etc., résolvant ainsi des problèmes ouverts posés par Alvarado et al. (2019).

Contexte et Motivation de la Recherche

Importance du Problème

1. Signification théorique: Le problème de sandwich de graphes est un problème classique en théorie des graphes, introduit par Golumbic et al. en 1995, constituant une généralisation naturelle des problèmes de reconnaissance de graphes
2. Complexité computationnelle: Les problèmes de sandwich sont au moins aussi difficiles que les problèmes de reconnaissance correspondants, et leur classification en complexité est un sujet important en théorie algorithmique des graphes
3. Problèmes ouverts: La complexité du problème de sandwich pour les graphes parfaits reste indéterminée et est considérée comme l'un des problèmes ouverts les plus importants du domaine

Limitations des Méthodes Existantes

1. Absence de cadre unifié: Les recherches existantes utilisent principalement des techniques spécialisées pour des classes de graphes particulières, manquant d'une méthode d'analyse générale
2. Preuves complexes: Les preuves traditionnelles de dureté nécessitent généralement des constructions de réduction complexes
3. Outils théoriques limités: Absence d'outils théoriques systématiques pour analyser la complexité des problèmes de sandwich

Motivation de la Recherche

Cet article vise à établir un lien entre les problèmes de sandwich de graphes et les problèmes de satisfaction de contraintes, en utilisant les outils matures de la théorie CSP pour fournir un cadre d'analyse unifié aux problèmes de sandwich.

Contributions Principales

1. Établissement d'un cadre théorique: Démonstration que les problèmes de sandwich de classes de graphes satisfaisant certaines conditions sont équivalents aux CSP de graphes à 2-coloration d'arêtes
2. Nouveaux résultats de complexité: Classification de complexité nouvelle pour plusieurs classes de graphes, notamment:
   • Versions multigraphes et multigraphes bipartis des graphes de lignes
   • Graphes parfaits $K_k$-libres
   • Graphes $\{I_4,P_4\}$-libres, etc.
3. Résolution de problèmes ouverts: Résolution du problème ouvert posé par Alvarado et al. (2019) concernant le problème de sandwich pour les graphes $\{I_4,P_4\}$-libres
4. Résultats de non-dichotomie: Construction de problèmes de sandwich de graphes coNP-intermédiaires, démontrant la non-trivialité de la classification en complexité

Détails de la Méthode

Définition de la Tâche

Problème de Sandwich de Graphes (SP): Étant donnée une classe de graphes $\mathcal{C}$ et une entrée $(V,E_1,E_2)$ où $E_1 \subseteq E_2$, déterminer s'il existe $E$ tel que $E_1 \subseteq E \subseteq E_2$ et $(V,E) \in \mathcal{C}$.

Formulation équivalente: L'entrée est un triplet $(V,E,N)$, où $E$ est l'ensemble des arêtes obligatoires et $N$ est l'ensemble des arêtes interdites, déterminer s'il existe un graphe $(V,E') \in \mathcal{C}$ tel que $E \subseteq E'$ et $E' \cap N = \emptyset$.

Cadre Théorique Principal

Graphes à 2-Coloration d'Arêtes et CSP

• Graphes à 2-coloration d'arêtes: Triplet $(V,B,R)$, où $B$ est l'ensemble des arêtes bleues et $R$ est l'ensemble des arêtes rouges, avec $B \cap R = \emptyset$
• Homomorphisme: Fonction de sommet préservant les relations d'adjacence et les couleurs
• CSP$(H)$: Classe de tous les graphes finis à 2-coloration d'arêtes pouvant être homomorphiquement mappés à $H$

Théorème de Caractérisation Principal

Proposition 3: Pour une classe de graphes $\mathcal{C}$, les énoncés suivants sont équivalents:

1. $\mathcal{C}$ est héréditaire, possède la propriété d'amalgamation conjointe et est fermée sous dilatation fractionnée
2. Il existe un graphe à 2-coloration d'arêtes $(V,R,B)$ tel que CSP$(V,R,B) = \text{SP}(\mathcal{C})$
3. Il existe un graphe $H$ tel que SP$(\mathcal{C}) = \text{CSP}(H^*) = \text{injCSP}(H^*)$

où $H^*$ désigne le graphe complet à 2-coloration d'arêtes, avec les arêtes bleues étant $E(H)$ et les arêtes rouges étant $N(H)$.

Points d'Innovation Technique

1. Constructions Primitives Positives

Utilisation de constructions pp pour établir des relations de réduction entre CSP, correspondant aux réductions par gadget en théorie des graphes.

2. Théorie des Graphes Universels

Pour une classe de graphes héréditaire $\mathcal{C}$, s'il existe un graphe universel $H$ (c'est-à-dire Age$(H) = \mathcal{C}$), alors SP$(\mathcal{C}) = \text{CSP}(H^*)$.

3. Fermeture sous Dilatation Fractionnée

• Dilatation: Ajout de jumeaux (sommets avec le même voisinage)
• Co-dilatation: Ajout de co-jumeaux (sommets avec le même voisinage sauf l'un l'autre)
• Dilatation fractionnée: Dilatation ou co-dilatation selon une partition de sommet $(I,C)$

Configuration Expérimentale

Vérification Théorique

Cet article est principalement un travail théorique, dont la validité est vérifiée par:

1. Reproduction de résultats connus: Reprouver les résultats de complexité connus des problèmes de sandwich en utilisant la méthode CSP
2. Dérivation de nouveaux résultats: Obtenir de nouvelles classifications de complexité en utilisant les outils de la théorie CSP
3. Vérification computationnelle: Les polymorphismes de certaines structures finies sont vérifiés par programme informatique

Outils d'Analyse

• Programmes Datalog: Résolution de certains CSP solubles en temps polynomial
• Réductions MMSNP: Réduction des CSP à domaine infini aux CSP à domaine fini
• Méthodes algébriques: Analyse de la complexité CSP utilisant les polymorphismes

Résultats Expérimentaux

Résultats Principaux de Complexité

1. Graphes de Lignes Associés

• Théorème: Le problème de sandwich pour les graphes de lignes de multigraphes est NP-complet
• Théorème: Le problème de sandwich pour les graphes de lignes de multigraphes bipartis est NP-complet

2. Classes à Sous-graphes Interdits

• Corollaire 18: Pour $k \geq 4$, les problèmes de sandwich pour les graphes $\{P_4,K_k\}$-libres, les graphes $\{P_4,I_k\}$-libres et les graphes parfaits $K_k$-libres sont tous NP-complets
• Théorème 17: Soit $F$ un ensemble de graphes non complètement déterminants par sommet et les graphes $F$-libres sont parfaits, alors pour $k \geq 4$, le problème de sandwich pour les graphes $(F \cup \{K_k\})$-libres est NP-difficile

3. Chemins Interdits

• Théorème 20: Pour $n,k \geq 4$, le problème de sandwich pour les graphes $\{P_n,K_k\}$-libres est NP-complet

Classification de la Complexité Algorithmique

Cas Solubles en Temps Polynomial

• Graphes fractionnés: Via réduction 2-SAT
• Graphes de seuil: Utilisant la polymorphie complètement symétrique
• Graphes multipartis complets: Résolution par programme Datalog

Cas NP-complets

• Graphes de comparabilité: Via réduction CSP d'ordre partiel aléatoire
• Graphes de permutation: Via réduction du problème d'intermédiarité
• Graphes fractionnés généralisés: Graphes $(p,q)$-fractionnés quand $p+q > 2$

Résultats de Non-Dichotomie

Théorème 21: Si P $\neq$ coNP, alors il existe une classe de graphes $\mathcal{C}$ telle que SP$(\mathcal{C})$ soit coNP-intermédiaire.

La construction est basée sur une adaptation du théorème de Ladner, démontrant que la complexité des problèmes de sandwich de graphes dépasse la dichotomie P vs NP.

Travaux Connexes

Recherche sur les Problèmes de Sandwich de Graphes

• Golumbic et al. (1995): Première étude systématique des problèmes de sandwich de graphes
• Travaux ultérieurs: Classification de complexité pour des classes de graphes spécifiques
• Problèmes ouverts: Complexité du problème de sandwich pour les graphes parfaits non déterminée

Théorie de la Satisfaction de Contraintes

• Théorème de Schaefer: Dichotomie pour les CSP sur domaine booléen
• Théorème de Hell-Nešetřil: Classification des problèmes d'homomorphisme de graphes
• Dichotomie pour domaine fini: Résultats révolutionnaires de Bulatov et Zhuk
• CSP à domaine infini: Classification de cas spéciaux comme les CSP temporels

Connexions Techniques

Cet article établit pour la première fois un lien systématique entre les problèmes de sandwich de graphes et les CSP à domaine infini, offrant une nouvelle perspective pour l'intersection de ces deux domaines.

Conclusion et Discussion

Conclusions Principales

1. Unification théorique: Les problèmes de sandwich de graphes peuvent être systématiquement analysés en utilisant la théorie CSP
2. Efficacité de la méthode: Les outils CSP simplifient les preuves de complexité et découvrent de nouveaux résultats
3. Richesse de la complexité: Les problèmes de sandwich exhibent un spectre complet de complexité allant de P à coNP-intermédiaire

Limitations

1. Portée d'application: Applicable uniquement aux classes de graphes satisfaisant certaines conditions (héréditaire, JEP, fermeture sous dilatation fractionnée)
2. Problème des graphes parfaits: Le problème ouvert le plus important (problème de sandwich pour les graphes parfaits) reste non résolu
3. Constructivité: Certains résultats d'existence manquent d'algorithmes de construction efficaces

Directions Futures

1. Structures ω-catégoriques: Étude des problèmes de sandwich pour les classes de graphes ω-catégoriques
2. Problème des graphes parfaits: Recherche de solutions au problème de sandwich pour les graphes parfaits
3. Décidabilité: Étude de la décidabilité de la complexité étant donné un ensemble de sous-graphes interdits
4. NP-intermédiaire: Recherche de problèmes de sandwich de graphes NP-intermédiaires

Évaluation Approfondie

Avantages

1. Innovation théorique: Établissement pour la première fois d'un lien systématique entre les problèmes de sandwich de graphes et la théorie CSP, fournissant un cadre d'analyse unifié
2. Élégance de la méthode: Utilisation d'outils CSP comme les constructions pp simplifie considérablement les preuves de complexité
3. Richesse des résultats: Résolution de plusieurs problèmes ouverts, fournissant de nombreux nouveaux résultats de complexité
4. Profondeur technique: Combinaison de théories profondes de la théorie des graphes, de la théorie des modèles et de la complexité computationnelle

Insuffisances

1. Restrictions d'application: Le cadre s'applique uniquement à des types spécifiques de classes de graphes, n'étant pas complètement universel
2. Applicabilité pratique: Contributions principalement théoriques, améliorations algorithmiques pratiques limitées
3. Graphes parfaits: Le problème ouvert central reste non résolu

Impact

1. Valeur académique: Fournit de nouveaux outils théoriques et perspectives pour la recherche sur les problèmes de sandwich de graphes
2. Signification interdisciplinaire: Favorise la fusion interdisciplinaire entre la théorie des graphes et la théorie CSP
3. Contribution méthodologique: L'application des constructions pp à l'analyse de complexité en théorie des graphes a une valeur exemplaire

Scénarios d'Application

Cette méthode est particulièrement adaptée à:

1. Classes de graphes héréditaires avec bonnes propriétés structurelles
2. Classes de graphes possédant des graphes universels
3. Problèmes de théorie des graphes nécessitant une analyse systématique de complexité

Références Bibliographiques

L'article cite 61 références connexes, incluant principalement:

• Travaux fondateurs sur les problèmes de sandwich de graphes 38
• Résultats fondamentaux de la théorie CSP 20,59,60
• Résultats de classification des CSP à domaine infini 10,11,46
• Résultats structurels en théorie des graphes 22,23,37,47

Résumé: En établissant un lien profond entre les problèmes de sandwich de graphes et les problèmes de satisfaction de contraintes, cet article fournit un cadre d'analyse théorique entièrement nouveau pour ce problème classique de théorie des graphes. Bien qu'il subsiste des limitations dans la résolution complète de tous les problèmes de sandwich, ses contributions théoriques et innovations méthodologiques ouvrent de nouvelles voies pour la recherche connexe.