Le calcul de la constante de Cheeger d'un graphique , également connu sous le nom de constante isopérimétrique (car il s'agit essentiellement d'un rapport surface / volume minimum), est connu pour être NP-complet. Elle est généralement approximative. Je voudrais savoir si des algorithmes polynomiaux exacts sont connus pour des classes spéciales de graphes. Par exemple, est-il toujours NP-complet pour les graphiques réguliers ? Pour les graphiques à distance régulière ? (Je n'ai pas étudié les preuves d'exhaustivité de NP existantes pour examiner leurs hypothèses.) Les pointeurs de la littérature sont appréciés - merci!
ds.algorithms
reference-request
graph-algorithms
Joseph O'Rourke
la source
la source
Réponses:
Notez que l'approximation de la coupe la plus éparse à donne une approximation de pour la constante de Cheeger telle que définie. Voici quelques articles qui donnent des algorithmes d'approximation constante pour la coupe la plus éparse dans les graphiques restreints:α 2 α
Genre délimité: http://dl.acm.org/citation.cfm?id=1873619
Largeur d'arbre limitée: http://arxiv.org/abs/1006.3970
De plus, http://arxiv.org/abs/1006.3970v2 prouve que la coupe la plus clairsemée est NP-difficile pour les graphiques avec la largeur de chemin 2, et a pas mal plus de références à l'approximation de la coupe la plus clairsemée sur les instances restreintes.
Je suppose que pour toutes les classes de graphiques mentionnées dans l'article, aucun algorithme exact n'est connu (car il s'intéresse aux approximations). En particulier, si la coupe la plus clairsemée est NP-difficile pour les graphiques avec pathwidth 2, elle est également NP-difficile pour les graphiques de treewidth 2 et cutwidth 2. Je suppose que cela ne donne pas beaucoup de place .. peut-être y a-t-il un autre meilleur paramétrage pour la coupe la plus clairsemée.
Je suis à peu près sûr que la coupe la plus éparse est NP-difficile sur les graphiques réguliers, mais je ne trouve pas de référence.
Per a remarqué que je n'avais pas fait attention quand j'ai regardé les papiers ci-dessus. Le résultat de la dureté est pour une coupe non uniforme plus clairsemée. Le calcul de la coupe uniforme la moins dense ou de la constante de Cheeger est facile sur les arbres (WLOG, la coupe optimale sépare un sous-arbre). Avec un peu plus de travail qui donne un algorithme de programmation dynamique pour calculer la constante de Cheeger sur des graphiques à largeur d'arbre bornée.
Le tableau 1 du document 2 ci-dessus mentionne également un résultat qui donne une approximation constante pour les graphiques avec un mineur exclu.
la source
Pour une solution exacte dans les graphiques planaires, voir Park et Phillips, STOC 93 . Il s'agit essentiellement de la coupe uniforme la moins dense, avec la différence mineure que leur dénominateur est | S | au lieu de | S | * | VS |. Comme l'a souligné Per, le cas des demandes non uniformes est différent.
la source