Complexité du comptage du nombre de couvertures de bord d'un graphique

Un couvercle de bord est un sous-ensemble de bords d'un graphique de sorte que chaque sommet du graphique est adjacent à au moins un bord du couvercle. Les deux articles suivants indiquent que le comptage des couvertures de bord est # P-complet: Un FPTAS simple pour compter les couvertures de bord et générer des couvertures de bord de graphiques de chemin . Cependant, à moins que j'aie manqué quelque chose, ils ne fournissent pas de référence pour cette réclamation, ni de preuve. (La référence 3 du premier article semblait prometteuse, mais je n'y ai pas trouvé non plus ce que je voulais.)

Où puis-je trouver une référence ou une preuve du fait que compter le nombre de couvertures de bord d'un graphique est # P-complet?

reference-request graph-algorithms counting-complexity proofs a3nm
la source

Réponses:

Je ne sais pas où cela a été prouvé pour la première fois, mais comme EdgeCover a une expression en tant que problème Holant de domaine booléen, il est inclus dans de nombreux théorèmes de dichotomie Holant.

EdgeCover est inclus dans le théorème de dichotomie dans (1). Le théorème 6.2 (dans la version journal ou le théorème 6.1 dans la préimpression) montre que EdgeCover est # P-dur sur les graphiques planaires à 3 niveaux. Pour voir cela, l'expression pour EdgeCover comme un problème Holant sur des graphes à 3 régularités est (ou remplacez par contenant 1 pour le même problème sur $\operatorname{Holant}([0,1,1,1])$ $[0,1,1,1]$ $[0,1,\dotsc,1]$ $k$ $k$ - graphiques réguliers). Cette notation répertorie la sortie d'une fonction symétrique par ordre de poids de Hamming en entrée. Pour un sous-ensemble des arêtes définies (que nous considérons comme étant affectées à 1 et l'ensemble complémentaire étant affecté à 0), la contrainte à chaque sommet est qu'au moins une arête est affectée à 1, ce qui est exactement ce que la fonction . Pour un sous-ensemble fixe d'arêtes, son poids est le produit des sorties de $[0,1,1,1]$ $[0,1,1,1]$ $[0,1,1,1]$ à chaque sommet. Si un sommet n'est pas couvert, il contribue à un facteur de . Si tous les sommets sont couverts, alors tous les sommets contribuent à un facteur de , donc le poids est également . Ensuite, le Holant doit additionner tous les sous-ensembles possibles d'arêtes et ajouter le poids correspondant à chaque sous-ensemble. Cette valeur Holant est exactement la même si nous subdivisons chaque arête et imposons la contrainte que les deux arêtes incidentes à ces nouveaux sommets doivent être égales. En utilisant la notation de fonction symétrique, cette fonction d'égalité binaire est . Ce graphique est bipartite. Les sommets d'une partie ont le $0$ $1$ $1$ $[1,0,1]$ tandis que les sommets de l'autre partie ont lacontrainte . L'expression de ce problème Holant est . Ensuite, vous pouvez vérifier par vous-même la ligne " " et la colonne " $[0,1,1,1]$ $[1,0,1]$ $\operatorname{Holant}([0,1,1,1]|[1,0,1])$ $[0,1,1,1]$ $[1,0,1]$ "du tableau près du théorème cité ci-dessus contient" H ", ce qui signifie que le problème est # P-difficile même le graphe d'entrée doit être plan.

Note latérale: Notez que Pinyan Lu est l'auteur à la fois de cet article et du premier article que vous citez. Je suppose que lorsque leur article dit que "compter les couvertures de bord est un problème # P-complet même lorsque nous limitons l'entrée à 3 graphiques réguliers", ils citaient implicitement (1). Ils n'ont probablement pas mentionné que la dureté tient également lorsqu'elle est encore limitée aux graphiques planaires, car leur FPTAS n'a pas besoin de cette restriction.

Plus tard, les théorèmes de dichotomie de Holant, tels que ceux de (2,3) --- versions de conférence et de journal du même ouvrage --- se sont avérés plus probants. Le théorème 1 (dans les deux versions) dit que EdgeCover est # P-dur sur les graphes planaires réguliers pour . Pour voir cela, nous devons appliquer une transformation holographique. Comme décrit ci-dessus, l'expression pour EdgeCover comme un problème Holant sur graphes réguliers est , où contient $k$ $k \ge 3$ $k$ $\operatorname{Holant}([0,1,\dotsc,1])$ $[0,1,\dotsc,1]$ $k$ 1. Et de plus, cela équivaut à . Maintenant, nous appliquons une transformation holographique par $\operatorname{Holant}([1,0,1]|[0,1,\dotsc,1])$ $T = \begin{bmatrix} 1 & e^{\pi i / k} \\ 1 & 0 \end{bmatrix}$ (ou son inverse, selon votre point de vue). Selon le théorème de Holant de Valiant (4,5), cela ne change pas la complexité du problème (en fait, les deux problèmes sont en fait le même problème car ils sont d'accord sur la sortie de chaque entrée ... seule l'expression du problème a changé ). L’expression alternative de ce problème est

où est la fonction d'égalité sur

Holant ([1, 0, 1] T^{\otimes 2} | (T^{- 1})^{\otimes k} [0, 1, \dots, 1]) = Holant ([2, e^{π i / k}, e^{2 π i / k}] | =_{k}),

$\operatorname{Holant}([1,0,1] T^{\otimes 2}|(T^{-1})^{\otimes k} [0,1,\dotsc,1]) = \operatorname{Holant}([2, e^{\pi i / k}, e^{2 \pi i / k}]|=_k),$

=_{k}

$=_k$

k

$k$ entrées. Pour appliquer le théorème 1, nous devons normaliser

en divisant la fonction d'origine par

, ce qui ne change pas la complexité du problème puisque cette valeur est non nulle. Ensuite, les valeurs

[2, e^{π i / k}, e^{2 π i / k}]

$[2, e^{\pi i / k}, e^{2 \pi i / k}]$

[2 e^{- π i / k}, 1, e^{π i / k}]

$[2 e^{-\pi i / k}, 1, e^{\pi i / k}]$

e^{π i / k}

$e^{\pi i / k}$

X

$X$

Y

$Y$

X = 2

$X = 2$

Y = - 2^{k} - 1

$Y = -2^k - 1$

k \geq 3

$k \ge 3$

k

$k$

k \geq 3

$k \ge 3$

Note latérale: On peut également voir ce théorème et cette preuve dans la thèse de Michael Kowalczyk .

Je poursuivrai ma recherche documentaire pour voir qu'EdgeCover s'est avéré être # P-difficile avant (1).

(1) Réduction, interpolation et dureté holographiques par Jin-Yi Cai, Pinyan Lu et Mingji Xia ( journal , préimpression ).

$k$ $\{0,1\}$

(4) Algorithmes holographiques de Leslie G. Valiant

(5) Théorème de Holant de Valiant et tenseurs d'allumettes par Jin-Yi Cai et Vinay Choudhary

Tyson Williams
la source

Wow, merci de m'avoir indiqué cela et d'avoir pris le temps d'expliquer le vocabulaire et la connexion à la couverture de bord! Je suis d'accord avec vous que (1) prouve implicitement que EdgeCover est difficile (et est difficile même pour les graphes planaires à 3 réguliers). Je suis également intéressé de savoir si quelqu'un a prouvé la dureté # P d'EdgeCover avant (1), bien que je sois déjà très heureux d'avoir quelque chose à citer si j'ai besoin d'utiliser ce résultat (ce qui était ma principale préoccupation lorsque j'ai demandé ). Merci encore pour votre réponse!

a3nm

@Tyson Williams: si vous commencez à partir d'un graphe 2-3 régulier et contractez les nœuds de la partition de degré 2, vous pourriez vous retrouver avec un multigraphe 3 régulier , c'est-à-dire avec des bords parallèles. Est-ce que cela peut être corrigé pour montrer la dureté sur des graphiques simples à 3 régularités ? Plus généralement, cette question pourrait être posée pour tous les résultats sur les problèmes Holant, j'ai donc créé une nouvelle question ici cstheory.stackexchange.com/q/43912/38111 , car je pense que le problème n'est pas limité à ce problème particulier (bord de comptage couvertures). Je serais heureux si vous pouviez jeter un coup d'œil :)

M.Monet

Ah oui. Bonne observation. Je ne peux pas me souvenir pour l'instant des résultats obtenus pour les graphiques simples.

Tyson Williams

@TysonWilliams: Merci d'avoir confirmé, et pas de soucis! Dans ma communauté, "graph" signifie toujours "simple graph" sauf indication contraire, donc je ne l'avais pas dit explicitement dans la question.

a3nm

@TysonWilliams: après tout, nous avons trouvé comment obtenir un résultat de dureté sur les couvertures de bord de comptage pour les graphiques simples (qui sont 2-3 bipartites et planaires réguliers) via des moyens holographiques. Les détails se trouvent dans la dernière version de ma réponse ci-dessous, et dans l'annexe D de arxiv.org/abs/1703.03201 . Nous utilisons la dureté du comptage des couvertures de sommets sur les graphes planaires bipartites à 3 régularités de xia2006regular: ces graphes n'ont pas d'auto-boucles, nous subdivisons chaque arête ce qui supprime les arêtes parallèles, et cai2008holographic ne crée pas de problèmes. (Quant aux graphiques à 3 réguliers, comme dans votre réponse, nous ne savons pas.)

a3nm

Après quelques recherches bibliographiques supplémentaires, il semble que la complexité du comptage des couvertures de bord dans un graphique s'est avérée être # P-complète dans bordewich2008path, Annexe A.1 . (Cela suppose des graphiques arbitraires en entrée, c'est-à-dire qu'ils ne peuvent appliquer aucune hypothèse sur le graphique d'entrée, sauf qu'ils observent que le degré minimal peut être rendu arbitrairement grand). (bordewich2008path indique en outre que le résultat est revendiqué sans preuve dans bubley1997graph.) Ce résultat est antérieur à ceux de Cai, Lu et Xia référencés comme (1) dans la réponse de Tyson Williams, et il ne s'appuie pas sur la théorie holographique.

Plus précisément, le résultat repose sur la dureté # P du comptage d'ensembles indépendants dans des graphiques à 3 réguliers montrés dans greenhill2000complexity (améliorant le résultat analogue pour les graphiques de degré au plus 4 montrés dans vadhan1997complexity), et prouve le résultat en utilisant la technique de bubley1997graph .

Un résultat plus fort, à savoir la dureté du comptage des couvertures de bord dans un graphique bipartite de degré au plus quatre (imposant en outre que le jeu de bords peut être divisé en quatre correspondances) a été étudié indépendamment dans khanna2011queries, Annexe B.1, toujours sans outils holographiques . Ils s'appuient sur la dureté du comptage d'ensembles indépendants dans des graphes bipartites à 3 réguliers (représentés dans xia2006regular par un raffinement de la méthode d'interpolation de la complexité vadhan1997) puis ils appliquent un raffinement de la technique de bordewich2008path.

Un résultat encore plus fort (la dureté des couvertures de bord de comptage dans un graphique régulier bipartite 2-3, c'est-à-dire un graphique bipartite où tous les sommets d'un côté ont le degré 2 et tous les sommets de l'autre côté ont le degré 3, qui est en plus plan)) peut être montré en utilisant les résultats de xia2006regular et cai2008holographic. Les explications à ce sujet figurent à l'annexe D de la dernière version de notre document PODS'17 . Dans ce cas, nous avons vérifié assez attentivement que le résultat est valable pour les graphes simples , c'est-à-dire pour les graphes qui n'ont ni auto-boucles ni multi-arêtes (voir les commentaires de la réponse de Tyson Williams).

Pour la dureté sur les graphes planaires à 3 régularités, un argument est donné dans la réponse de Tyson Williams, mais il semblerait qu'il autorise les arêtes multiples et les boucles automatiques dans les graphes.

Les références:

bordewich2008path: Magnus Bordewich, Martin Dyer, Marek Karpinski, Path Coupling Using Stopping Times and Counting Independent Sets and Colorings in Hypergraphs , 2008.
bubley1997graph: Russ Bubley, Martin Dyer, Orientations du graphique sans puits et une approximation pour un cas dur de #SAT , 1997. Aucune version en libre accès ne semble disponible en ligne. :-(
cai2008holographic: J. Cai, P. Lu, M. Xia, Réduction holographique, interpolation et dureté , 2008
greenhill2000complexity: Catherine Greenhill, La complexité du comptage des colorations et des ensembles indépendants dans les graphiques clairsemés et les hypergraphes , 2000
khanna2011queries: Sanjeev Khanna, Sudeepa Roy, Val Tannen, requêtes avec différence sur les bases de données probabilistes , 2011.
vadhan1997complexity: Salil P. Vadhan, The Complexity of Counting in Sparse, Regular, and Planar Graphs , 1997. Certains résultats sont probablement apparus à l'origine dans une thèse, mais je n'ai pas vérifié.
xia2006regular: Mingji Xia, Wenbo Zhao, # 3-Regular Bipartite Planar Vertex Cover is # P-Complete , 2006. Aucune version en libre accès ne semble disponible en ligne. :-( Notez que le premier auteur est également un auteur de (1) dans la réponse de Tyson Williams.

Diclaimer: Je n'ai eu qu'un aperçu superficiel de ces articles et je ne suis pas un expert dans ce domaine, il peut donc y avoir des erreurs dans mon résumé ci-dessus.

Merci à un arbitre anonyme PODS'17 de m'avoir pointé sur khanna2011queries, c'est ce qui m'a poussé à écrire cette réponse.

a3nm
la source