Algorithme parallèle déterministe pour une correspondance parfaite dans les graphiques généraux?

Dans la classe de complexité , il y a des problèmes supposés NE PAS être dans la classe , c'est-à-dire des problèmes avec des algorithmes parallèles déterministes. Le problème du débit maximal en est un exemple. Et il y a des problèmes que l'on croyait être dans , mais aucune preuve n'a encore été trouvée.N C N $\mathsf{P}$$\mathsf{NC}$$\mathsf{NC}$

L' appariement parfait problème est l' un des plus problème fondamental soulevé en théorie des graphes: étant donné un graphe , il faut établir une correspondance parfaite pour . Comme j'ai pu le trouver sur Internet, malgré le bel algorithme polynomial Blossom de Edmonds et un algorithme parallèle RANDOMISÉ par Karp, Upfal et Wigderson en 1986, seules quelques sous-classes de graphiques sont connues pour avoir des algorithmes .G N $G$$G$$\mathsf{NC}$

En janvier 2005, un article du blog Computational Complexity prétend qu'il reste ouvert que Perfect Matching soit dans . Ma question est:$\mathsf{NC}$

Y a-t-il eu des progrès depuis lors, au-delà de l' algorithme randomisé ?$\mathsf{NC}$

Pour clarifier mon intérêt, tout algorithme qui traite des graphes GÉNÉRAUX est sympa. Bien que les algorithmes pour les sous-classes de graphiques soient également corrects, cela peut ne pas être à mon attention. Merci à tous!

EDIT au 27/12:

Merci pour toute votre aide, j'essaie de résumer tous les résultats en une seule figure:

Les classes connues les plus basses contiennent les problèmes suivants:

• Correspondance dans les graphiques généraux: [ KUW86 ], [ CRS93 ]R N C$\mathsf{RNC}$$\mathsf{RNC}^2$
• Correspondance dans les graphes bipartites du genre planaire / constant: / [ DKT10 ] / [ DKTV10 ]S P $\mathsf{UL}$$\mathsf{SPL}$
• Correspondance lorsque le nombre total est polynomial: [ H09 ]$\mathsf{SPL}$
• Correspondance maximale Lex-first: [ MS89 ]$\mathsf{CC}$

En outre, sous l'hypothèse de complexité plausible: nécessite des circuits exponentiels, la correspondance dans les graphiques généraux se trouve dans [ ARZ98 ].S P $\mathsf{SPACE[n]}$$\mathsf{SPL}$

$NC$ algorithmes pour les correspondances parfaites dans les graphiques généraux sont toujours ouverts mais des progrès ont été accomplis. Voici quelques-uns que je connais:

Pour les graphiques généraux, Agrawal-Hoang-Thierauf a montré qu'étant donné la promesse que le nombre de correspondances parfaites est petit, il existe un algorithme pour les énumérer tous.$NC^2$

Pour la classe des graphes planaires, le pfaffian joue un grand rôle. Kastelyn a montré comment chaque graphe planaire peut être orienté de manière à ce que le pfaffian soit exactement égal au nombre de correspondances parfaites. (Cela a été utilisé par Valiant pour donner des " algorithmes holographiques " pour divers problèmes) Mahajan-Subramanya-Vinay a montré comment le pfaffian peut être calculé en utilisant des modifications des séquences de clow. (Kastelyn donne en fait un algorithme pour trouver l'incorporation dans mais je ne sais pas si l'incorporation pfaffian peut également être calculée en ; si oui, cela signifierait que le comptage des correspondances parfaites dans les graphiques planaires est en .)P N C N $NC$$P$$NC$$NC$

Et un résultat récent de Vinodchandran-Tewari montre que le lemme d'isolement peut être "dérandomisé" pour les graphes planaires (en utilisant le théorème de Green!) Pour mettre l'accessibilité planaire dans . Mais les algorithmes pour les appariements planaires sont toujours ouverts (merci à Raghunath d'avoir corrigé mon affirmation selon laquelle il est en ). Datta-Kulkarni-Roy a donné un algorithme pour les appariements planaires bipartitesN C U L N $UL$$NC$$UL$$NC$

J'espère que cela t'aides.

Quelques années plus tard :) et Perfect Matching est maintenant connu pour être en quasi-NC (c'est-à-dire que vous avez besoin de processeurs quasi-polynomiaux). Voir l'article de Fenner, Gurjar et Thierauf (pour les graphiques bipartites) https://arxiv.org/pdf/1601.06319.pdf et notre travail avec Ola Svensson (pour les graphiques généraux): https://arxiv.org/pdf/1704.01929

La dérandomisation du lemme d'isolement par Tewari-Vinodchandran ne donne malheureusement pas de limite supérieure UL sur l'appariement planaire. En fait, je ne pense même pas qu'un algorithme NC ne soit pas connu pour la correspondance planaire. Mais dans un travail récent avec Datta, Kulkarni et Nimbhorkar, nous montrons une limite supérieure UL sur l'appariement plan bipartite (la rédaction de ce résultat est toujours en cours). Ceci est intéressant car auparavant, même une liaison NL n'était pas connue pour ce problème.

Lorsqu'un problème d'optimisation est connu pour être difficile, il est habituel de regarder leurs versions maximales. Par exemple, alors que l'ensemble indépendant est NP-Complete, le premier ensemble indépendant maximal lex, qui est P-Complete.

Dans le même ordre d'idées, bien que nous ne connaissions pas la complexité exacte de Perfect Matching, la première correspondance maximale lex a été étudiée et est connue pour être CC-complète (CC signifie des problèmes qui peuvent être résolus par des circuits de comparaison de taille polynomiale). Il s'avère que la solution parallèle la plus connue de cette classe a depth. Une grande partie de tout cela devrait être trouvée dans cet article de Mayr, Subramanian.$\sqrt n$

Tous ces points indiquent qu'il n'y a peut-être pas de version NC facilement parallélisable pour cela. Mais alors qui sait? Quelqu'un pourrait dérandomiser la version RNC la semaine prochaine!

Edit: Merci Ramprasad. Mais voici un autre lien vers le document.

Les résultats d'approximations parallèles peuvent éclairer la complexité parallèle de l'appariement parfait. Fischer, Goldberg, Haglin et Plotkin ont conçu un algorithme parallèle pour trouver approximativement la correspondance de cardinalité maximale qui pose le problème d'approximation en . Leur algorithme utilise processeurs et s'exécute en temps .N C n Θ ( 1 / ϵ ) O ( log 3 n $(1-\epsilon)-$$NC$$n^{\Theta(1/\epsilon)}$$O(\log^3 n)$

T. Fischer, AV Goldberg, DJ Haglin et S. Plotkin. Rapprochement d'appariements en parallèle. Info. Proc. Lett., 46 (3): 115, 1993