Un graphe H est un noyau si tout homomorphisme de H vers lui-même est une bijection. Un sous-graphe H de G est un noyau de G si H est un noyau et qu'il y a un homomorphisme de G vers H. http://en.wikipedia.org/wiki/Core_%28graph_theory%29
Étant donné un graphe G, quel est l'algorithme exact le plus connu pour trouver son noyau?
ds.algorithms
graph-theory
graph-algorithms
Régularité
la source
la source
Réponses:
Calculer le noyau d'un graphe est difficile: même décider si un graphe donné à 3 couleurs est un noyau est co-NP-complet, voir Hell and Nesetril . Il existe des paramètres où le calcul de base peut être effectué efficacement, voir Efficient Core Computation in Data Exchange de Georg Gottlob et Alan Nash pour un paramètre de base de données; ici, certaines restrictions raisonnables sur les types de contraintes dans le schéma de base de données permettent de calculer efficacement les cœurs.
Edit: Mis à part le travail Gottlob / Nash mentionné ci-dessus, je ne connais aucune autre tentative de fournir des algorithmes efficaces pour le calcul de base. Des pointeurs vers des algorithmes meilleurs que la force brute (exacte ou non) seraient les bienvenus.
la source
Le problème de déterminer si un graphe donné est un graphe central est facilement perçu comme étant en co-NP. En fait, il est co-NP complet.
Le problème de déterminer si un sous-graphe donné H est un noyau d'un graphe G donné est dans la classe DP plus large ( https://complexityzoo.uwaterloo.ca/Complexity_Zoo:D#dp ), et est en fait complet pour cette classe ( le problème archétypique complet pour cette classe consiste en paires de formules booléennes, où la première est satisfaisable et la seconde est insatifiable). Le confinement dans DP est clair: testez que G mappe de façon homomorphe à H (cela est codé comme satisfiabilité) et simultanément que H n'a pas d'homomorphisme sur lui-même qui n'est pas sur (ceci est codé comme insatisfaisabilité). La dureté DP n'est pas triviale et est prouvée dans l'article:
Fagin, Ronald, Phokion G. Kolaitis et Lucian Popa. "Échange de données: aller au cœur du problème." ACM Transactions on Database Systems (TODS) 30.1 (2005): 174-210.
la source