Complejidad de contar el número de cubiertas de borde de un gráfico

Una cubierta de borde es un subconjunto de bordes de un gráfico de tal manera que cada vértice del gráfico es adyacente al menos a un borde de la cubierta. Los siguientes dos artículos dicen que las cubiertas de borde de conteo, se #P -Complete: A FPTAS simples para el recuento de cubiertas de cuchilla y Cubiertas Generación de borde de gráficos Path . Sin embargo, a menos que me haya perdido algo, no proporcionan una referencia para este reclamo ni una prueba. (La referencia 3 del primer artículo parecía prometedora, pero tampoco encontré lo que quería allí).

¿Dónde puedo encontrar una referencia o prueba del hecho de que contar el número de cubiertas de borde de un gráfico es # P-completo?

No sé dónde se demostró esto por primera vez, pero dado que EdgeCover tiene una expresión como un problema de Holant de dominio booleano, está incluido en muchos teoremas de dicotomía de Holant.

EdgeCover se incluye en el teorema de dicotomía en (1). El teorema 6.2 (en la versión de diario o el teorema 6.1 en la preimpresión) muestra que EdgeCover es # P-hard sobre gráficos planos 3 regulares. Para ver esto, la expresión de EdgeCover como un problema de Holant en gráficos de 3 regulares es (o reemplace [ 0 , 1 , 1 , 1 ] con [ 0 , 1 , ... , 1 ] que contiene k 1 para el mismo problema sobre $\operatorname{Holant}([0,1,1,1])$$[0,1,1,1]$$[0,1,\dotsc,1]$$k$$k$-Gráficos regulares). Esta notación enumera la salida de una función simétrica en orden de peso de Hamming de entrada. Para algún subconjunto de los bordes del conjunto (que consideramos que se le asigna 1 y el conjunto del complemento se le asigna 0), la restricción en cada vértice es que al menos un borde se le asigna 1, que es exactamente lo que la función [ 0 , 1 , 1 , 1 ] . Para un subconjunto fijo de bordes, su peso es el producto de las salidas de [ 0 , 1 , 1 , 1 $[0,1,1,1]$$[0,1,1,1]$$[0,1,1,1]$en cada vértice Si algún vértice no está cubierto, contribuye con un factor de . Si todos los vértices están cubiertos, todos los vértices contribuyen con un factor de 1 , por lo que el peso también es 1 . Luego, Holant debe sumar todos los subconjuntos posibles de bordes y agregar el peso correspondiente a cada subconjunto. Este valor de Holant es exactamente el mismo si subdividimos cada borde e imponemos la restricción de que ambos bordes incidentes a estos nuevos vértices deben ser iguales. Usando la notación de función simétrica, esta función de igualdad binaria es [ 1 , 0 , 1 ] . Este gráfico es bipartito. Los vértices en una parte tienen el [ 0 , 1 $0$$1$$1$$[1,0,1]$ mientras que los vértices en la otra parte tienen larestricción [ 1 , 0 , 1 ] . La expresión para esto como un problema de Holant es Holant ( [ 0 , 1 , 1 , 1 ] | [ 1 , 0 , 1 ] ) . Luego puede verificar por sí mismo esa fila " [ 0 , 1 , 1 , 1 ] " y la columna " [ 1 , $[0,1,1,1]$$[1,0,1]$$\operatorname{Holant}([0,1,1,1]|[1,0,1])$$[0,1,1,1]$ "de la tabla cerca del teorema citado anteriormente contiene" H ", lo que significa que el problema es # P-hard incluso el gráfico de entrada debe ser plano.$[1,0,1]$

Nota al margen: tenga en cuenta que Pinyan Lu es autor de este documento y del primer documento que cita. Supongo que cuando su artículo dice "contar las cubiertas de los bordes es un problema # P-completo incluso cuando restringimos la entrada a 3 gráficos regulares", estaban citando implícitamente (1). Probablemente no mencionaron que la dureza también se mantiene cuando se restringe aún más a los gráficos planos, ya que su FPTAS no necesita esta restricción.

Más tarde, los teoremas de dicotomía de Holant, como los de las versiones (2,3) (conferencias y revistas del mismo trabajo) demostraron más. El teorema 1 (en ambas versiones) dice que EdgeCover es # P-hard sobre los gráficos planas regulares para k ≥ 3 . Para ver esto, necesitamos aplicar una transformación holográfica. Como se describió anteriormente, la expresión de EdgeCover como un problema de Holant sobre gráficos k regulares es Holant ( [ 0 $k$$k \ge 3$$k$ , donde [ 0 , 1 , ... , 1 ] contiene$\operatorname{Holant}([0,1,\dotsc,1])$$[0,1,\dotsc,1]$$k$1's. Y además, esto es equivalente a . Ahora aplicamos una transformación holográfica por T = [ 1 e π i / k 1 0$\operatorname{Holant}([1,0,1]|[0,1,\dotsc,1])$$T = \begin{bmatrix} 1 & e^{\pi i / k} \\ 1 & 0 \end{bmatrix}$(o su inverso, dependiendo de su perspectiva). Según el Teorema de Holant de Valiant (4,5), esto no cambia la complejidad del problema (de hecho, ambos problemas son en realidad el mismo problema porque están de acuerdo en la salida de cada entrada ... solo la expresión del problema ha cambiado ) La expresión alternativa para este problema es

donde = k es la función de igualdad en

$$\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$ entradas. Para aplicar el Teorema 1, tenemos que normalizar [ 2 , e π i / k , e 2 π i / k ] a [ 2 e - π i / k , 1 , e π i / k ] dividiendo la función original por e π i / k , que no cambia la complejidad del problema ya que este valor no es cero. Entonces los valores X e$k$$[2, e^{\pi i / k}, e^{2 \pi i / k}]$$[2 e^{-\pi i / k}, 1, e^{\pi i / k}]$$e^{\pi i / k}$$X$$Y$en el enunciado del teorema son e Y = - 2 k - 1 . Para k ≥ 3 , se puede verificar que este problema, por lo tanto, EdgeCover también es # P-duro sobre los gráficos planas k- regulares para k ≥ 3 .$X = 2$$Y = -2^k - 1$$k \ge 3$$k$$k \ge 3$

Nota al margen: también se puede ver este teorema y prueba en la tesis de Michael Kowalczyk .

Continuaré mi búsqueda de literatura para ver que EdgeCover demostró ser # P-hard antes (1).

(1) Reducción holográfica, interpolación y dureza por Jin-Yi Cai, Pinyan Lu y Mingji Xia ( diario , preimpresión ).

(2) Una dicotomía para -Gráficos regulares con { 0 , 1 } -Asignaciones de vértices y funciones de borde real$k$$\{0,1\}$ por Jin-Yi Cai y Michael Kowalczyk.

(3) Funciones de partición en -Gráficos regulares con { 0 , 1 } -Asignaciones de vértices y funciones de borde real$k$$\{0,1\}$ de Jin-Yi Cai y Michael Kowalczyk.

(4) Algoritmos holográficos de Leslie G. Valiant

(5) Teorema Holant de Valiant y tensores de compuerta de Jin-Yi Cai y Vinay Choudhary

Después de un poco más de búsqueda bibliográfica, parece que la complejidad de contar las cubiertas de los bordes en un gráfico demostró ser # P-completa en bordewich2008path, Apéndice A.1 . (Esto supone gráficos arbitrarios como entrada, es decir, no pueden hacer cumplir ninguna suposición en el gráfico de entrada, excepto que observan que el grado mínimo puede hacerse arbitrariamente grande). (bordewich2008path indica además que el resultado se reivindica sin pruebas en el gráfico de bubley1997). Este resultado es anterior a los de Cai, Lu y Xia a los que se hace referencia como (1) en la respuesta de Tyson Williams, y no se basa en la teoría holográfica.

Específicamente, el resultado se basa en la dureza # P de contar conjuntos independientes en gráficos de 3 regulares que se muestran en la complejidad greenhill2000 (mejorando el resultado análogo para gráficos de grado como máximo 4 que se muestran en la complejidad de vadhan1997), y demuestra el resultado usando la técnica de bubley1997graph .

Un resultado más fuerte, a saber, la dureza de contar las cubiertas de los bordes en un gráfico bipartito de grado como máximo cuatro (imponiendo aún más que el conjunto de bordes se puede dividir en cuatro coincidencias) se estudió de forma independiente en khanna2011consultas, Apéndice B.1, nuevamente sin herramientas holográficas . Dependen de la dureza de contar conjuntos independientes en gráficos bipartitos 3-regulares (mostrados en xia2006 regular por un refinamiento del método de interpolación de complejidad vadhan1997) y luego aplican un refinamiento de la técnica de bordewich2008path.

Un resultado aún más fuerte (la dureza de contar las aristas de los bordes en un gráfico bipartito 2-3 regular, es decir, un gráfico bipartito donde todos los vértices de un lado tienen grado 2 y todos los vértices del otro lado tienen grado 3, que además es plano) se mostrará utilizando los resultados de xia2006regular y cai2008hologgraphic. Las explicaciones para esto aparecen como Apéndice D de la última versión de nuestro documento PODS'17 . En este caso, verificamos con bastante cuidado que el resultado se cumple para gráficos simples , es decir, para gráficos que no tienen auto-bucles ni múltiples bordes (ver los comentarios a la respuesta de Tyson Williams).

En cuanto a la dureza de las gráficas planas de 3 regulares, se da un argumento en la respuesta de Tyson Williams, pero parece que permite múltiples aristas y bucles automáticos en las gráficas.

Referencias

• bordewich2008path: Magnus Bordewich, Martin Dyer, Marek Karpinski, Path Coupling Using Stopping Times and Counting Sets and Colourings in Hypergraphs , 2008.
• bubley1997graph: Russ Bubley, Martin Dyer, Orientaciones sin sumidero y una aproximación para un caso difícil de #SAT , 1997. Parece que no hay disponible una versión de acceso abierto en línea. :-(
• cai2008 holográfica: J. Cai, P. Lu, M. Xia, reducción holográfica, interpolación y dureza , 2008
• greenhill2000complejidad: Catherine Greenhill, La complejidad de contar colores y conjuntos independientes en gráficos e hipergrafías dispersas , 2000
• khanna2011consultas: Sanjeev Khanna, Sudeepa Roy, Val Tannen, Consultas con diferencia en bases de datos probabilísticas , 2011.
• Complejidad de vadhan1997: Salil P. Vadhan, La complejidad de contar en gráficos dispersos , regulares y planos , 1997. Algunos resultados probablemente aparecieron originalmente en una tesis, pero no lo comprobé.
• xia2006regular: Mingji Xia, Wenbo Zhao, # 3-Bipartite Planar Vertex Cover es # P-Complete , 2006. Parece que no hay una versión de acceso abierto disponible en línea. :-( Tenga en cuenta que el primer autor también es autor de (1) en la respuesta de Tyson Williams.

Diclaimer: solo tuve una mirada superficial a estos documentos y no soy un experto en este campo, por lo que puede haber errores en mi resumen anterior.

Gracias a un árbitro anónimo de PODS'17 por señalarme a khanna2011queries, que es lo que me llevó a escribir esta respuesta.