Existe-t-il une réduction directe / naturelle pour compter les correspondances parfaites non bipartites en utilisant le permanent?

Compter le nombre de correspondances parfaites dans un graphe bipartite est immédiatement réductible au calcul du permanent. Étant donné que trouver une correspondance parfaite dans un graphique non bipartite est dans NP, il existe une certaine réduction des graphiques non bipartites au permanent, mais cela peut impliquer une explosion polynomiale désagréable en utilisant la réduction de Cook à SAT puis le théorème de Valiant pour réduire à la permanent.

Une réduction efficace et naturelle d'un graphe non bipartite vers une matrice où serait utile pour une implémentation réelle pour compter les correspondances parfaites en utilisant des solutions existantes fortement optimisées bibliothèques qui calculent le permanent. $f$ $G$ $A = f(G)$ $\operatorname{perm}(A) = \Phi(G)$

Mise à jour: j'ai ajouté une prime pour une réponse comprenant une fonction efficacement calculable pour prendre un graphe arbitraire dans un graphe bipartite avec le même nombre de correspondances parfaites et pas plus de sommets. $G$ $H$ $O(n^2)$

graph-theory counting-complexity reductions permanent Derrick Stolee
la source

Le titre actuel ressemble à une question de devoirs, mais la vraie question est beaucoup plus intéressante que cela. Je n'ai presque même pas ouvert la question b / c, je pensais que c'était des devoirs et serait bientôt fermé, jusqu'à ce que je vois qu'il avait déjà 9 votes positifs et que je suis devenu curieux ... Peut-être changer le titre en quelque chose de plus dans le sens de: " Existe-t-il une réduction directe / naturelle pour compter les correspondances parfaites non bipartites en utilisant le permanent? "

Joshua Grochow

Bonne idée. Je n'y ai même pas pensé. Merci.

Derrick Stolee

Nitpicking: "Puisque la recherche d'une correspondance parfaite dans un graphique non bipartite est dans NP" → "Puisque le comptage des correspondances parfaites dans un graphique non bipartite est dans #P"

Tsuyoshi Ito

Votre piqûre est correcte, et j'ai envisagé de l'écrire, mais la façon dont je l'ai écrit laisse entendre que la réduction s'applique aux réductions de Cook's THEN Valiant. Je recherche une réduction directe et efficace.

Derrick Stolee du

Il y a une réduction qui évite Cook: écrivez d'abord une formule VNP pour des correspondances parfaites (je peux penser à une qui est très similaire à celle pour le permanent et qui a une taille

). Ensuite, par l'universalité du permanent, cela peut s'écrire comme le permanent d'une matrice de taille

. Cela utilise le fait qu'une formule de taille

peut être écrite comme le permanent d'une matrice de taille

. Plus direct que de passer par Cook, mais toujours pas aussi direct / naturel que la façon dont perm compte les correspondances parfaites dans un graphique bipartite.

\leq 4 n^{4}

$\leq 4n^4$

4 n^{4} + 1

$4n^4 +1$

S

$S$

S + 1

$S+1$

Joshua Grochow

Réponses:

Je dirais qu'une réduction "simple" de l'appariement bipartite est hautement improbable. Premièrement, cela donnerait un algorithme pour trouver une correspondance parfaite dans un graphique général en utilisant la méthode hongroise. Par conséquent, la réduction devrait contenir toute la complexité de l'algorithme de la fleur d'Edmond. Deuxièmement, cela donnera un LP compact pour un polytope parfaitement adapté et, par conséquent, la réduction ne devrait pas être symétrique (qui est exclue par un résultat de Yannakakis) et intrinsèquement très compliquée.

Mohit Singh
la source

Ce sont toutes de bonnes raisons pour lesquelles il est peu probable que cela existe. J'aurais dû demander des réfutations dans la question. Je vais probablement donner un peu de bonté à cette réponse, à moins que quelqu'un ne vous prouve le contraire.

Derrick Stolee

Bien que ce ne soit pas la réponse que je voulais, j'ai trouvé cette réponse très satisfaisante.

Derrick Stolee

@MohitSingh Pourriez-vous s'il vous plaît élaborer «la non-existence de la méthode hongroise pour les graphiques non bipartites», «qu'est-ce qui contient toute la complexité de l'algorithme de floraison» et pourquoi cela donnerait-il «LP compact pour une correspondance parfaite et ne devrait donc pas être symétrique» ?

T ....

C'est évidemment un commentaire et non une réponse, mais je n'ai pas encore de points de réputation ici, alors désolé.

Pour les graphes cubiques sans pontage non bipartites, il existe de manière exponentielle de nombreuses correspondances parfaites, comme Lovàsz et Plummer le conjecturaient dans les années 70. Le document est en préparation. Cela peut être très pertinent pour votre question, ou peut-être pas du tout.

Andrew D. King
la source