Questions marquées «graph-isomorphism»

Supposons que et G 2 soient deux graphes non dirigés sur l'ensemble de sommets { 1 , … , n } . Les graphiques sont isomorphes si et seulement s'il y a une permutation Π de telle sorte que G 1 = Π ( G 2 ) , ou plus formellement, s'il y a une permutation Π de telle sorte que ( i , j ) est une arête...

Le problème de l’isomorphisme graphique (IG) est sans doute le candidat le mieux connu pour un problème NP-intermédiaire . L'algorithme le plus connu est l'algorithme sous-exponentiel avec la durée d'exécution . On sait que GI n’est pas complet sauf si la hiérarchie polynomiale...

Étant donné un nouveau problème dans dont la véritable complexité se situe quelque part entre et NP-complete, il existe deux méthodes que je connais qui pourraient être utilisées pour prouver que la résolution de ce problème est difficile:NPNP\mathsf{NP}PP\mathsf{P} Montrer que le problème est...

Non - déterminisme Borné associe une fonction avec une classe C des langues acceptées par les machines de Turing déterministe borné ressources, pour former une nouvelle classe g - C . Cette classe se compose des langages acceptés par une machine de Turing non déterministe M obéissant aux mêmes...

Il est facile de voir que l' isomorphisme graphique (GI) est en NP. C'est un problème ouvert majeur si l'IG est en coNP. Existe-t-il des candidats potentiels aux propriétés des graphiques qui peuvent être utilisés comme certificats IG de coNP? Des conjectures impliquant ? Quelles sont les...

Je suppose que j'ai lu trop de documents ambitieux du CdRR . Le problème est que ces articles ne sont pas examinés par des pairs, mais semblent souvent intéressants et passent des contrôles de plausibilité de base. Ou peut-être pas, et j'ai juste besoin d'améliorer mes contrôles de plausibilité....

J'essaie de comprendre la relation entre l'isomorphisme des graphes et le problème des sous-groupes cachés. Y a-t-il une bonne référence pour

Cela fait plus d'un an depuis sa rétractation et sa correction de janvier 2017. Y a-t-il des nouvelles? Sinon, est-ce normal que la validation prenne autant de temps? Je m'attendrais à ce qu'il retienne beaucoup d'attention Quelqu'un de remarquable a-t-il parlé pour soutenir / douter du résultat...

Motivé par le commentaire de Fortnow sur mon article, Preuve que le problème d'isomorphisme graphique n'est pas completNPNPNP G I N P N P P G I P , et par le fait que est un candidat principal pour le problème intermédiaire (pas complet ni en ), je suis intéressé par des preuves connues que se...

Inspiré par la question de l' affacturage connu pour être P-dur , je me demande quel est l'état similaire actuel des connaissances sur la dureté de l'isomorphisme du graphe. Je suis sûr que l'on ne sait pas actuellement si GI est en P, mais: quelle est la plus grande classe actuellement connue que...

En réfléchissant à la complexité du test de l'isomorphisme des graphes asymétriques (voir ma question connexe sur la théorie), une question complémentaire m'est venue à l'esprit. Supposons que nous ayons une machine de Turing à temps polynomial qui en entrée génère un graphe avec nœuds.1 n G M , n...

Actuellement, je fais une étude documentaire sur le problème d'isomorphisme graphique (GI). J'aimerais connaître quelques questions ouvertes concernant les points suivants Quels sont les paramètres du graphique pour lesquels la tractabilité des paramètres fixes de l'IG est un problème ouvert. Quels...

Je lis sur les classes de graphiques pour lesquels Graphique Isomorphisme ( ) est en . Un de ces cas est des graphiques de valence bornée (maximum sur le degré de chaque sommet) comme expliqué ici . Mais je l'ai trouvé trop abstrait. Je serais reconnaissant si quelqu'un pouvait me suggérer quelques...

Je fais une revue de la littérature sur le problème d'isomorphisme graphique. La plupart des articles que je lis sont écrits par EM Luks et Laszlo Babai. Ces articles utilisent les connaissances de haut niveau de la théorie des groupes et de la théorie de la complexité. Comme je suis nouveau dans...

Étant donné le groupe de symétrie et deux sous-groupes et , ? G , H ≤ S n π ∈ S n G π ∩ H = ∅SnSnS_nG,H≤SnG,H≤SnG, H\leq S_nπ∈Snπ∈Sn\pi\in S_nGπ∩H=∅Gπ∩H=∅G\pi\cap H=\emptyset Pour autant que je sache, le problème est connu sous le nom de problème d'intersection de coset. Je me demande quelle est la...

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...

Ce problème m'intéresse: étant donné un graphe non orienté , y a-t-il une partition de en graphes et tels que etG(E,V)G(E,V)G(E, V)GGGG1(E1,V1)G1(E1,V1)G_1(E_1, V_1)G2(E2,V2)G2(E2,V2)G_2(E_2, V_2)G1G1G_1G2G2G_2 sont isomorphes? Ici, est partitionné en deux ensembles disjoints et . Les ensembles et...

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:...

Dans l'article An Efficient Algorithm for Graph Isomorphism de Corneil et Gotlieb, 1970, une conjecture a été énoncée sur laquelle l'algorithme énoncé s'est appuyé pour résoudre l'IG en temps polynomial. À savoir: que les graphiques représentatifs présentent la partition d'automorphisme du...

On ne sait pas si isomorphisme de graphes (IG) pour les graphiques fortement réguliers (SRGS) est en P . Y a-t-il des indices qu'il pourrait ou non être GI- Complet? Y a-t-il des conséquences importantes dans de tels cas? (Similaire à la croyance que l'IG peut ne pas être