Complejidad de contar todas las subgrafías conectadas

Deje que G sea un gráfico conectado.

¿Cuál es la complejidad de contar todos los subgrafos conectados si G es de los siguientes tipos?

G es general.

G es plano.

G es bipartito.

No me importan las estructuras o ... ¡solo necesito contar todas las subgrafías conectadas! También estoy interesado en la complejidad de contar todas las subgrafías conectadas con exactamente k nodos en G.

Punteros a los papeles y libros también son bienvenidos!

cc.complexity-theory graph-theory counting-complexity marjoonjan
fuente

¿Sabe que la lista de la pregunta no está formateada correctamente? meta.cstheory.stackexchange.com/questions/300/… Si no le importa el formateo, está bien. Pero no estoy seguro de si alguien quiere dedicar tiempo a responder su pregunta cuando usted no quiere dedicar tiempo a formatearla correctamente. (No digo que sepa la respuesta)

Tsuyoshi Ito

Además, ¿le importa enumerar subgrafías conectadas de tamaño / orden / estructura / ... arbitraria, o desea que abarquen o cualquier otra cosa?

Anthony Labarre

Parece que hay trabajo en contar subgrafías que se extienden conectadas . La página 32 del "polinomio Tutte multivariado" de Sokal conecta el polinomio de subgrafo que abarca con el polinomio de confiabilidad que tiene una gran literatura

Yaroslav Bulatov

Lo siento, mi respuesta anterior sobre el uso del teorema de Kirchhoff fue incorrecta. Pensé en un argumento de inclusión-exclusión, pero esto podría no ser factible.

Didest

Este documento no es exactamente lo que solicitó, pero el documento y sus referencias pueden ayudarlo a desarrollar algunas ideas.

MS Dousti

Respuestas:

Galés afirma que el problema # P-completo incluso en el caso más restringido (contando el número de subgrafías conectadas de un gráfico bipartito plano). Consulte la parte inferior de la página 305 en Gales, Dominic (1997), "Recuento aproximado", Surveys in Combinatorics , Bailey, RA, ed., Cambridge University Press, págs. 287–324.

En contexto, sin embargo, me pregunto si realmente se refiere a subgrafos conectados. Y eso me lleva a preguntarme qué versión del problema desea: ¿subgrafos conectados, subgrafos conectados que no necesitan ser abarcados, o subgrafos inducidos conectados?

David Eppstein
fuente

Esta es una respuesta a la respuesta de David. Sin haber mirado aún ese libro, supongo que el problema es contar subgrafos conectados, porque este es el punto x = 1 y = 2 del polinomio de Tutte, y el autor estaba interesado en eso. Pero, de hecho, creo que esos tres problemas se reducen fácilmente al contar el problema del subgrafo de expansión conectado. Las siguientes reducciones deberían funcionar para el conteo exacto o la aproximación, aunque creo que el problema para la aproximación aún está abierto.

$K_A$ $A$

$\#P$

Colin McQuillan
fuente

No necesita adjuntar una camarilla, ¿verdad? Puede adjuntar cualquier cosa que tenga muchas subgrafías conectadas, siempre que adjunte lo mismo a cada vértice. Por lo tanto, podría hacer estas reducciones preservando tanto la planaridad como la bipartididad.

David Eppstein