Comptage des instances de sous-graphe

Disons que j'ai un grand graphique (plusieurs milliers de nœuds) orienté G et un graphe orienté beaucoup plus petit (3-5 nœuds) g. Je veux compter combien d'isomorphismes de g sont en G. En d'autres termes, je veux savoir combien de jeux de nœuds uniques dans G correspondent g. Je réalise qu'il s'agit d'une instance du problème d'isomorphisme de sous-graphe et est donc NP-complet. Cependant, étant donné que vous pouvez supposer que g est petit, existe-t-il un algorithme raisonnablement efficace pour le faire?Comptage des instances de sous-graphe

Source

2010-11-23 dsimcha

Peut-être que le http://math.stackexchange.com/ vous donnerait de meilleurs résultats - Je sais ce que vous cherchez est un algorithme, mais vous pourriez probablement concevoir un algorithme de la théorie – veljkoz

Est-ce que votre problème "un cas" ou vous voulez un algorithme général. Je demande juste parce que certaines caractéristiques sur la cardinalité des bords de g peuvent aider beaucoup ... –

Si la taille de votre plus petit graphe ne croît pas en fonction de N, alors même un algorithme de force brute devrait être un temps polynomial, parce que N choisit k est O (N^k). – mbeckish

Bien que l'isomorphisme des graphes soit NP-complet en général, les problèmes que vous rencontrez dans le monde réel sont souvent assez faciles. Une simple force brute devrait suffire: Soit M_i un ensemble de cartes depuis les i premiers nœuds de g vers les nœuds de G. Commencer avec m_0 contenant la carte vide et l'étendre un nœud à la fois, en écartant toutes les cartes qui violent la contrainte x->y ss m(x)->m(y).

Vous aurez besoin de commander les noeuds en g de sorte que beaucoup d'élagage se fasse tôt. En supposant que vos graphiques sont assez clairsemés, vous aurez besoin d'un ordre qui complète autant d'arêtes que possible, peut-être un dfs du plus haut degré.

Source

2010-11-23 19:44:10

Je pensais à cela avant, mais je pensais qu'il pourrait y avoir une solution plus intelligente. Il s'avère que cela ne prend que quelques secondes à courir pour les tailles de problèmes que je travaille avec. Je suppose que la leçon est d'éviter de trop compliquer les choses. – dsimcha

Répondre

Questions connexes