Recuento de subgrafos de grafos bipartitos

Question

No soy teórico de grafos ni especialista en complejidad computacional, así que pido disculpas si esta pregunta es estúpida o está mal planteada.

Dado un grafo bipartito $G$ de $n$ vértices, cuántos subgrafos inducidos de $m\leq n$ vértices para los que el número total de aristas del subgrafo es impar? O, ¿cuál es la complejidad computacional de hacer tal determinación?

Una manera de reformular esto es tomar una cadena de bits $y\in\{0,1\}^n$ de forma que cada bit $y_k$ especifica si se mantiene o no el $k^{th}$ vértice. Entonces la cuestión consiste en contar el número de instancias satisfactorias de $\bigoplus_{\{k,l\}\in E}y_ky_l=1$ donde $E$ denota las aristas de $G$ y limitado por el requisito de que el peso Hamming de $y$ es $m$ .

Aunque me interesa un resultado para todos los grafos bipartitos, también me interesa el caso especial de la red cuadrada. No he sido capaz de encontrar exactamente este problema en cualquier lugar, pero hay un par de casos que creo que han sido contestadas:

• Si no hay restricción para que el grafo sea bipartito, el problema es agudo-P completo [N. Creignou, H. Schnoor e I. Schnoor, Informática Logic 5213, 109 (2008), Springer Berlin].
• Si, en cambio, no tenemos la restricción a la $m$ -vertex subgraphs, y sólo preguntar cuántos subgrafos inducidos hay con un número impar de aristas, existe un algoritmo eficiente para contarlos [A. Ehrenfeucht y M. Karpinski, The Computational Complexity of (XOR, AND)-Counting Problems, Technical Report 90-033 (1990)].

Answer 1

No sé la respuesta, sólo algunas ideas.

Suponga que tiene $n$ vértices del primer tipo y $l$ del segundo. Por supuesto, usted sabe la respuesta si no hay ninguna restricción en el número de aristas (usted quiere que sea impar). Por lo tanto equivalentemente puedo calcular casos, cuando es impar con coeficiente (-1) y casos, cuando es par con coeficiente 1 (denoto esta cantidad por $N$ ). Sea $y_1,\dots,y_n,z_1,\dots,z_l$ sean elementos de $\mathbb{Z}\_2=\mathbb{Z}/(2\mathbb{Z})$ correspondientes a los vértices del grafo. Las aristas vienen dadas por $n\times l$ matriz $A$ . Entonces $N$ es el coeficiente de $h^m$ en $S(h,h)$ donde $S$ se define por $$S(h,g)=\sum_{y\in\mathbb{Z}\_2^n,\;z\in\mathbb{Z}\_2^l} h^{|y|} g^{|z|} (-1)^{\sum_{i,j}y_i A_{ij} z_j}.\tag{1}$$ Aquí $|y|$ es la cantidad de componentes en $y\in \mathbb{Z}\_2^n$ que son iguales a $1$ . Uno puede deshacerse de la suma sobre $y\in\mathbb{Z}\_2^n$ de la siguiente manera: $$S(h,g)=\sum_{z\in\mathbb{Z}\_2^l} g^{|z|}\prod_{i=1}^{n} (1+h(-1)^{\sum_j A_{ij} z_j}).\tag{2}$$ Esto, por ejemplo, resuelve el problema en dos casos:
1. fijamos el número de vértices sólo en una parte de un grafo bipartito y el mapa $\mathbb{Z}_2^l\to\mathbb{Z}_2^n\colon z\mapsto x$ con $x_i=\sum_j A_{ij} z_j$ es suryectiva (en este caso podemos omitir $g^{|z|}$ en $(2)$ , haz el cambio de coordenadas descrito y aplica de nuevo el truco que utilizamos para obtener (2) a partir de (1));
2. la cantidad de vértices en una parte de un grafo bipartito es suficientemente pequeña (en este caso la suma (2) tiene un número de términos suficientemente pequeño y cada uno de ellos puede calcularse en un tiempo polinómico);

Answer 2

Por desgracia, no tengo respuesta. La siguiente observación me hace pensar que un solución inteligente de fuerza bruta está al alcance de la mano, e incluso puede encontrar su camino a una enumeración.

Si m fuera n-1, el problema sería fácil: determinar la paridad del número de aristas del grafo G, y determinar la paridad del grado de cada arista. A continuación, el número de subgrafos en n-1 vértices con un número impar de aristas es el mismo que el número de vértices cuyo grado tiene paridad opuesta a la paridad de G.

Ahora bien, si estuviera haciendo un algoritmo de fuerza bruta, y m satisficiera 2*m > n, entonces podría usar la observación anterior para mirar los subgrafos inducidos en (m+1) vértices y luego hacer los cálculos sobre un conjunto de cobertura de los (m+1) subgrafos. O podría haber una versión de 2 pasos en la que podría usar pares de vértices en un (m+2) subgrafo. Es tentador pensar que también hay una versión de (n-m)-pasos usando funciones generadoras o la enumeración de Polya, pero no sé lo suficiente como para hablarte de ellas.

Cuando pueda comentar, entonces puede que convierta esta cavilación de respuesta en comentario.

Gerhard "Ask Me About System Design" Paseman, 2010.02.04