Le problème ODD EVEN DELTA

Soit un graphe. Soitêtre un entier. Soit le nombre de sous-graphes induits par les arêtes de ayant sommets et un nombre impair d'arêtes. Soit le nombre de sous-graphes induits par les arêtes de ayant sommets et un nombre pair d'arêtes. Soit . Le problème ODD EVEN DELTA consiste à calculer , étant donné et . $G = ( V, E )$ $k \leq |V|$ $O_k$ $G$ $k$ $E_k$ $G$ $k$ $\Delta_k = O_k - E_k$ $\Delta_k$ $G$ $k$

Des questions

Est-il possible de calculer en temps polynomial? Quel est l'algorithme le plus connu pour le calculer? $\Delta_k$

Et si est 3-régulier? $G$

Et si est bipartite à 3 régularités? $G$

Que se passe-t-il si est bipartite planaire? $G$

ds.algorithms graph-theory graph-algorithms counting-complexity Giorgio Camerani
la source

Quelle est votre motivation?

Tyson Williams

@TysonWilliams: Ma motivation est que, si la 1ère partie de la 1ère question a une réponse affirmative (même uniquement pour le cas planaire bipartite 3-régulier), alors il y aurait des conséquences intéressantes méritant une exploration plus approfondie. Si l'algorithme est sous-exponentiel, il aurait quand même quelques conséquences (moins intéressantes, mais méritant néanmoins plus d'exploration).

Giorgio Camerani le

Peux-tu être plus précis? Qu'entendez-vous par "quelques conséquences intéressantes"? Comment avez-vous rencontré ce problème en premier lieu?

Tyson Williams

@TysonWilliams: Pouvons-nous poursuivre cette conversation en privé, par e-mail?

Giorgio Camerani le

Réponses:

Le problème ODD EVEN DELTA est # P-difficile, même sur les graphes planaires bipartites à 3 normales.

Laissez - l'ensemble des couvertures de sommets d'un graphe général . Ensuite, en supposant que n'a pas de sommets isolés, l'équation suivante est vraie (reportez-vous à l'article ci-dessus pour la preuve): $\mathcal{C}$ $G$ $G$

| C | = 2^{| V |} - \sum_{k = 2}^{| V |} Δ_{k} \cdot 2^{| V | - k}

$|\mathcal{C}| = 2^{|V|} - \sum_{k = 2}^{|V|} \Delta_k \cdot 2^{|V|-k}$

Le comptage des couvertures de sommets est # P-complet même sur des graphes planaires bipartites à 3 intervalles réguliers, et cela peut être fait avec un nombre linéaire d'appels vers un oracle ODD EVEN DELTA.

Giorgio Camerani
la source

MISE À JOUR:

J'aurais dû souligner que la réponse ci-dessous concerne le cas particulier de . Puisque ce cas est difficile, le problème pour général est également difficile. $k = |V|$ $k$

Le cadre Holant est essentiellement une somme exponentielle sur des sous-graphes s'étendant (c'est-à-dire que tous les sommets sont présents dans le sous-graphe, donc la somme est sur les sous-ensembles d'arêtes). En revanche, la version actuelle de la question concerne les sous-graphiques induits par les bords.

$|V|$

3-Graphes planaires réguliers

$G$

Pl-Holant ([1, 0, - 1] | [0, 1, 1, 1]) .

$\text{Pl-Holant}([1,0,-1]|[0,1,1,1]).$

Laissez-moi vous expliquer comment. Pour plus de détails que ceux que je fournis ci-dessous, consultez cet article .

Le Holant est une somme sur les affectations (booléennes) aux arêtes. Sur les sommets sont des contraintes dont les entrées sont les affectations à leurs bords incidents. Pour chaque affectation aux arêtes, nous prenons le produit de toutes les contraintes de sommet.

Votre exigence qu'il n'y ait pas de sommets isolés est la contrainte qui n'est pas satisfaite à un sommet particulier si aucune de ses arêtes incidentes n'est sélectionnée et est satisfaite si au moins une arête est sélectionnée. Cette contrainte symétrique est désignée par [0,1,1,1], qui génère 0 (c'est-à-dire insatisfait) lorsque le nombre d'entrées 1 est égal à 0 (c'est-à-dire aucun front incident dans le sous-graphique) et sort 1 (c'est-à-dire satisfait) lorsque le nombre des entrées 1 est 1, 2 ou 3 (c'est-à-dire 1, 2 ou 3 fronts incidents dans le sous-graphique).

$G$ $G$ $n$ $(-1)^n = 1$ $n$ $(-1)^n = -1$

Ce problème bipartite de Holant est # P-difficile par le théorème 6.1 dans cet article . Cependant, ce théorème n'est pas le plus facile à appliquer. Tenez plutôt compte des éléments suivants.

$T = \begin{bmatrix} -1 & 1 \\ 0 & 1 \end{bmatrix},$

\begin{aligned} Pl-Holant ([1, 0, - 1] | [0, 1, 1, 1]) & = Pl-Holant ([1, 0, - 1] T^{\otimes 2} | (T^{- 1})^{\otimes 3} [0, 1, 1, 1]) \\ = Pl-Holant ([1, - 1, 0] | [1, 0, 0, 1]) . \end{aligned}

$\begin{align*} \text{Pl-Holant}([1,0,-1]|[0,1,1,1]) &= \text{Pl-Holant}([1,0,-1] T^{\otimes 2}|(T^{-1})^{\otimes 3}[0,1,1,1])\\ &= \text{Pl-Holant}([1,-1,0]|[1,0,0,1]). \end{align*}$

Ensuite, il est facile de voir que ce problème est # P-difficile par le théorème 1.1 dans cet article .

Limiter aux graphiques bipartites

Tout comme votre question précédente , le même problème limité aux graphiques bipartites est beaucoup plus difficile à gérer et je pense que c'est toujours un problème ouvert. Nous avons une conjecture quant aux cas traitables (et je vérifierai si votre problème est l'un d'entre eux), mais je pense que votre problème est toujours # P-difficile même lorsqu'il est limité aux graphiques bipartis.

Tyson Williams
la source

Merci d'avoir consacré votre temps à cette question et d'avoir fourni une réponse aussi détaillée. N'étant pas familier avec le cadre Holant, j'aurai besoin d'un peu de temps pour l'analyser et métaboliser pleinement votre raisonnement (bien sûr, je n'ai aucun doute sur son exactitude, c'est juste que je veux comprendre chaque étape, pas seulement la conclusion) . Pour ce qui concerne la restriction de bipartisme, oui, ce serait vraiment bien si vous pouviez vérifier si votre conjecture de cas traitable englobe mon problème.

Giorgio Camerani,