El problema ODD INCLUSO DELTA

Deje ser un gráfico. Dejeser un número entero Sea el número de inducidas por aristas de tienen vértices y un número impar de aristas. Sea el número de inducidas por aristas de tienen vértices y un número par de aristas. Deje . El problema ODD EVEN DELTA consiste en calcular , dados y . $G = ( V, E )$ $k \leq |V|$ $O_k$ $G$ $k$ $E_k$ $G$ $k$ $\Delta_k = O_k - E_k$ $\Delta_k$ $G$ $k$

Preguntas

¿Es posible calcular en tiempo polinómico? ¿Cuál es el algoritmo más conocido para calcularlo? $\Delta_k$

¿Qué pasa si es 3-regular? $G$

¿Qué pasa si es bipartito 3-regular? $G$

¿Qué pasa si es bipartito planar 3-regular? $G$

ds.algorithms graph-theory graph-algorithms counting-complexity Giorgio Camerani
fuente

¿Cuál es tu motivación?

Tyson Williams

@TysonWilliams: Mi motivación es que, si la primera parte de la primera pregunta tiene una respuesta afirmativa (incluso solo para el caso bipartito planar 3-regular), entonces habría algunas consecuencias interesantes que merecen una mayor exploración. Si el algoritmo es sub-exponencial, aún tendría algunas consecuencias (menos interesante, pero merecedora de más exploración).

Giorgio Camerani

¿Puedes ser mas específico? ¿Qué quieres decir con "algunas consecuencias interesantes"? ¿Cómo encontraste este problema en primer lugar?

Tyson Williams el

@TysonWilliams: ¿Podríamos continuar esta conversación en privado, por correo electrónico?

Giorgio Camerani

Respuestas:

El problema ODD EVEN DELTA es # P-hard, incluso en gráficos planos bipartitos 3-regulares.

Deje el conjunto de cobertura de vértices de un gráfico en general . Luego, suponiendo que no tenga vértices aislados, se cumple la siguiente ecuación (consulte la prueba del artículo anterior): $\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}$

El conteo de las cubiertas de vértices es # P-completo incluso en gráficos planos bipartitos 3-regulares, y se puede hacer con un número lineal de llamadas a un oráculo ODD EVEN DELTA.

Giorgio Camerani
fuente

ACTUALIZAR:

Debería haber señalado que la respuesta a continuación es sobre el caso especial de . Como este caso es difícil, el problema para general también es difícil. $k = |V|$ $k$

El marco Holant es esencialmente una suma exponencial sobre subgrafos de expansión (es decir, todos los vértices están presentes en el subgrafo, por lo que la suma está sobre los subconjuntos de bordes). En contraste, la versión actual de la pregunta trata sobre subgrafías inducidas por bordes.

Una versión anterior de esta pregunta se refería a contar ciertos subgrafos sin vértices aislados. La siguiente respuesta aborda correctamente este requisito. Cuando se consideran ambos subgráficos de expansión (es decir, el marco de Holant) y no hay vértices aislados, esto es lo mismo que considerar los subgráficos inducidos por bordes con vértices El OP básicamente señaló esto en esta pregunta . $|V|$

3-Gráficos planos regulares

Por el momento, ignoraré su requisito de que el gráfico sea bipartito. $G$

Suponga que es un gráfico plano 3-regular. Su problema se puede expresar como el problema Holant planar bipartito $G$

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

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

Déjame explicarte cómo. Para obtener más detalles de los que proporciono a continuación, consulte este documento .

El Holant es una suma de asignaciones (booleanas) a los bordes. En los vértices hay restricciones cuyas entradas son las asignaciones a sus bordes incidentes. Para cada asignación a los bordes, tomamos el producto de todas las restricciones de vértice.

Su requisito de que no haya vértices aislados es la restricción que no se cumple en un vértice particular si no se selecciona ninguno de sus bordes incidentes y se cumple si se selecciona al menos un borde. Esta restricción simétrica se denota por [0,1,1,1], que genera 0 (es decir, insatisfecho) cuando el número de entradas 1 es 0 (es decir, no hay bordes incidentes en el subgrafo) y salidas 1 (es decir, satisfecho) cuando el número de entrada 1 es 1, 2 o 3 (es decir, 1, 2 o 3 bordes incidentes en el subgrafo).

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

Este problema bipartito de Holant es # P-difícil por el Teorema 6.1 en este documento . Sin embargo, ese teorema no es el más fácil de aplicar. En cambio, considere lo siguiente.

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

\begin{aligned} Pl-Holant ([1, 0 0, - 1] El | [0 0, 1, 1, 1]) & = Pl-Holant ([1, 0 0, - 1] T^{\otimes 2} El | (T^{- 1})^{\otimes 3} [0 0, 1, 1, 1]) \\ = Pl-Holant ([1, - 1, 0 0] El | [1, 0 0, 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*}$

Entonces es fácil ver que este problema es # P-difícil según el Teorema 1.1 en este documento .

Restringir a los gráficos bipartitos

Al igual que su pregunta anterior , el mismo problema restringido a los gráficos bipartitos es mucho más difícil de manejar y creo que sigue siendo un problema abierto. Tenemos una conjetura sobre los casos manejables (y comprobaré si su problema es uno de ellos), pero creo que su problema sigue siendo # P-difícil incluso cuando está restringido a gráficos bipartitos.

Tyson Williams
fuente

Gracias por dedicar su tiempo a esta pregunta y por haber proporcionado una respuesta tan detallada. Al no estar familiarizado con el marco Holant, necesitaré algo de tiempo para analizarlo y metabolizar completamente su razonamiento (por supuesto, no tengo dudas sobre su corrección, es solo que quiero entender cada paso, no solo la conclusión) . En lo que respecta a la restricción de bipartidismo, sí, sería realmente bueno si pudieras verificar si tu conjetura de casos manejables abarca mi problema.

Giorgio Camerani