Le cas des graphiques fortement réguliers est-il le plus difficile à tester GI? où "le plus dur" est utilisé dans un sens "commun", ou "en moyenne", pour ainsi dire. Wolfram MathWorld mentionne quelques "graphiques pathologiquement durs". Que sont-ils? Mon échantillon de 25 paires de graphiques:...
Le problème de l'automorphisme libre à points fixes demande un automorphisme de graphe qui déplace au moins k ( n ) nœuds. Le problème est N P -complet si k ( n ) = n c pour tout ckkkk(n)k(n)k(n)NPNPNPk(n)=nck(n)=nck(n)=n^cccc > 0. Cependant, si alors le problème est le temps polynomial Turing...
Considérons le problème suivant: étant donné un graphe de requête et un graphe de référence G ′ = ( V ′ , E ′ ) , nous voulons trouver la cartographie injective f : V → V ′ qui minimise le nombre d'arêtes ( v 1 , v 2 ) ∈ E tel que ( f ( v 1 ) , f ( v 2 ) )G=(V,E)G=(V,E)G = (V,...
L' algorithme Weisfeiler-Lehman 1-dim (WL) est communément appelé algorithme d'étiquetage canonique ou de raffinement des couleurs. Cela fonctionne comme suit: La coloration initiale est uniforme, C 0 ( v ) = 1 pour tous les sommets v ∈ V ( G ) ∪ V ( H ) .C0C0C_0C0( v ) = 1C0(v)=1C_0(v) = 1v ∈ V( G...
L'isomorphisme graphique ( ) est un bon candidat pour un problème intermédiaire . problèmes intermédiaires existent sauf si . Je recherche un problème naturel difficile pour sous réduction de Karp (Un problème graphique tel que ).GIGIGINPNPNPNPNPNPP=NPP=NPP=NPGIGIGIXXXGI<mpXGI<pmXGI...
GI et Knot Problem sont tous deux des problèmes de décision d'équivalence structurelle d'objets mathématiques. Y a-t-il des résultats établissant des liens entre eux? De jolies connexions du problème des nœuds à la physique statistique ont été explorées via des polynômes de nœuds , y a-t-il des...
Je révise un modèle cryptographique. Pour montrer son insuffisance, j'ai conçu un protocole artificiel basé sur l'isomorphisme des graphes. Il est "banal" (et pourtant controversé!) De supposer l'existence d'algorithmes BPP capables de générer "des instances dures du problème d'isomorphisme des...
Étant donné un groupe de permutations sur [ n ] = { 1 , ⋯ , n } , et deux vecteurs u , v ∈ Γ n où Γ est un alphabet fini qui n'est pas tout à fait pertinent ici, la question est de savoir s'il existe des π ∈ G tel que π ( u ) = v où π ( u ) signifie appliquer la permutation π sur u de manière...
J'ai une question (espérons-le simple, peut-être stupide) sur le document historique de Babai montrant que est quasipolynomial.G Igje\mathsf{GI} Babai a montré comment produire un certificat que deux graphes pour sont isomorphes, en temps quasi-polynomial dans.gje= ( Vje,
En lisant les questions exemples où l'unicité de la solution permet de trouver plus facilement , une nouvelle (? Plus facile) question est venue à l' esprit: en fait , nous ne savons pas si le graphique Isomorphisme ( problème) est dans P .G IgjeGIPPP Mais que se passe-t-il si nous supposons que et...
Je veux être très précis. Quelqu'un connaît-il un rejet ou une preuve de la proposition suivante: ∃p∈Z[x],n,k,C∈N,∃p∈Z[x],n,k,C∈N,\exists p \in \mathbb{Z}[x], n, k, C \in \mathbb{N}, ∀G,H∈STRUC[Σgraph](min(|G|,|H|)=n,G≄H),∀G,H∈STRUC[Σgraph](min(|G|,|H|)=n,G≄H),\forall G, H \in...
Quels sont les autres langages de problèmes différents de l'isomorphisme des graphes dans ? Pouvez-vous donner quelques références?NP∩ c o A MNP∩coAMNP\cap coAM Mise à jour: J'ai oublié de mentionner que je suis intéressé dans les langues ne sont pas connus pour être en .c o...
Imaginons que nous ayons deux ensembles mmm de points X,Y⊂RnX,Y⊂RnX,Y\subset \mathbb{R}^n . Quelle est la complexité (temporelle) des tests s'ils diffèrent uniquement par la rotation? : il existe une matrice de rotation OOT=OTO=IOOT=OTO=IOO^T=O^TO=I telle que X=OYX=OYX=OY ? Il y a un problème de...
Dans le célèbre contre-exemple de l'isomorphisme des graphes via la méthode de Weisfeiler-Lehman (WL), le gadget suivant a été construit dans cet article par Cai, Furer et Immerman. Ils construisent un graphe donné parXk= ( Vk, Ek)Xk=(Vk,Ek)X_k = (V_k, E_k) Vk= Ak∪ Bk∪ Mk où UNEk= { aje∣ 1 ≤ i ≤ k...
Il y a eu quelques efforts pour attaquer le problème d'isomorphisme des graphes en utilisant la marche aléatoire quantique des bosons à noyau dur (symétrique mais sans double occupation). La puissance symétrique de la matrice d'adjacence, qui semblait prometteuse, s'est révélée incomplète pour les...
Je suis intéressé à étudier les problèmes complets de l'isomorphisme graphique (GI). Dans le document "Problems Polynomially Equivalent to Graph Isomorphism" de Kellogg S. Booth, (1979), a prouvé que de nombreux problèmes de base sont GI complets en utilisant des techniques de remplacement des...
Une partie de la difficulté à en savoir plus sur ce problème est que le problème de correspondance des graphiques est différent de son cousin beaucoup plus célèbre, le problème de correspondance, mais difficile à en distinguer lors de l'utilisation des moteurs de recherche. Étant donné deux...
Je voudrais savoir s'il existe un résultat déjà publié à ce sujet: Nous prenons tous les chemins différents possibles entre chaque paire de nœuds de deux graphiques réguliers connectés (avec le degré disons et le nombre de nœuds ) et notons leurs longueurs. Bien sûr, ce nombre de chemins distincts...
Étant donné tout graphe simple non orienté G, il n'est pas trivial de déterminer si G a des automorphismes non triviaux (sans identité). Mais quels sont les résultats sur les bornes supérieures / inférieures de ce problème de
Le problème d'isomorphisme semi - groupe inverse fini est -il GI-complet ? Ici, les semi-groupes inverses finis sont supposés être donnés par leurs tables de