Problèmes ouverts liés à l'isomorphisme des graphes

18

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

  1. Quels sont les paramètres du graphique pour lesquels la tractabilité des paramètres fixes de l'IG est un problème ouvert.

  2. Quels sont les paramètres du graphe, en les fixant la solvabilité polynomiale temporelle de GI n'est pas connue.

  3. La complexité de l'IG lorsqu'elle est restreinte à de nombreuses classes de graphes est équivalente à l'IG générale (GI-Completeness). Quelles sont les classes de graphes pour lesquelles l'intégralité de l'IG n'est pas connue.

Je vous remercie.

graph-isomorphism fixed-parameter-tractable Kumar
la source
3
Je ne connais pas de réponse définitive à vos questions. Si vous trouvez des réponses partielles (ce qui pourrait nécessiter de consulter des dizaines de documents de recherche publiés), ce serait bien si vous pouviez créer un lien vers le résumé que vous créez ou donner ses points saillants comme réponse.
András Salamon
re 3, question. pour les nombreuses classes de graphes complète GI éprouvée, est la question « sont sans but graphiques GI complet? » ouvert? Cela a-t-il un sens? question cs.se connexeXX
vzn

Réponses:

13

Pour la première question: l'isomorphisme graphique a été considéré pour au moins les paramètres suivants pour lesquels la tractabilité à paramètres fixes est toujours ouverte.

  • pathwidth / treewidth (voir [2], a été demandé ici ), peut-être résolu: http://arxiv.org/abs/1404.0818
  • largeur de bande / bande passante [1]
  • treewidth-k taille du jeu de suppression de sommets (numéro de jeu de sommets de rétroaction dans [7])
  • largeur de distance arbre / chemin (voir [1]), largeur de distance arbre connecté (voir [3], mais vous pouvez vous rapprocher assez de la dernière, voir section 6.4. de ma thèse de diplôme ) : résolu par Y. Otachi et P Schweitzer: http://arxiv.org/abs/1403.7238
  • largeur de clique / profondeur d'arbuste (ou profondeur SC) (voir [ 4 ])
  • degré maximum [5]
  • genre [6] / numéro de croisement [8]

Notez qu'il existe des recherches actives en cours pour certains d'entre eux.

[1]: K. Yamazaki, HL Bodlaender, B. de Fluiter et DM Thilikos. Isomorphisme pour les graphiques de largeur de distance bornée. Algorithmica 24.2 (1999)

[2]: HL Bodlaender. Algorithmes polynomiaux pour l'isomorphisme des graphes et l'index chromatique sur les arbres partiels. Journal of Algorithms 11.4 (1990)

[3]: Y. Otachi. Isomorphisme pour les graphiques de largeur de chemin connecté connecté. Algorithmes et calcul. Springer, 2012

[ 4 ]: http://www.fi.muni.cz/~hlineny/res-en.html#recent

[5]: L. Babai et EM Luks. Étiquetage canonique des graphiques. STOC '83.

[6]: EST Filotti et JN Mayer. Un algorithme à temps polynomial pour déterminer l'isomorphisme des graphiques de genre fixe. STOC '80 / G. Miller. Test d'isomorphisme pour les graphiques du genre borné. STOC '80

[7]: S. Kratsch et P. Schweitzer. Isomorphisme pour les graphiques du nombre de sommets de rétroaction bornés. SWAT 2010

[8]: http://math.mit.edu/news/summer/SPURprojects/2012Velednitsky.pdf

frafl
la source
1
En termes de recherche pertinente et active dans ce domaine, il y a quelques références supplémentaires que je suggérerais. [A] Le présent document ici de l' IPEC 2012, le isomorphisme de montre est traitable paramètre fixé dans la arborescente profondeur d'un graphe, qui est un paramètre lié à la largeur de l' arbre. [B] Cet article montre ici que l'isomorphisme des graphes pour les graphes en accords est FPT dans la taille du plus grand composant simplicial.
Adam Bouland
3
Sg
@Adam Bouland Existe-t-il des algorithmes temporels FPT ou polynomiaux pour l'isomorphisme graphique pour la largeur de bande bornée.
Kumar
1
@Kumar Il est soluble dans le temps mais n'est pas connu comme FPT. Voir Yamazaki et al. [1] dans la réponse de frafl.
Yota Otachi
5

Pour la troisième question: le document d'enquête de Brandstadt, Le et Spinrad, Graph Classes: A Survey, SIAM, 1999, contient plusieurs classes de graphiques pour lesquelles l'IG n'est pas connu. L'une de ces classes est constituée par les graphes trapézoïdaux . Une autre classe est constituée par les graphes d'arc de cercle qui sont mentionnés comme problème ouvert dans l'introduction de l'article, Tractabilities and Intractabilities on Geometric Intersection Graphs par Uehara.

EDIT : Le problème d'isomorphisme graphique pour les tournois n'est pas connu pour être GI-complet.

Mohammad Al-Turkistany
la source
4

Pour la troisième question, vous pouvez également consulter le site www.graphclasses.org : lancez l'applet Java et sélectionnez Problèmes -> Problèmes aux limites / ouverts -> Isomorphisme du graphique.

Vous obtiendrez une énorme liste de classes de graphiques pour lesquelles l'état du problème GI est inconnu de l'ISGCI (il pourrait être en P ou GI-complet); probablement pour certains d'entre eux, l'intégralité de l'IG est déjà établie, ou simplement ils n'ont pas encore été étudiés; mais c'est un bon point de départ pour rechercher des articles à leur sujet.

Marzio De Biasi
la source