Problema de verificación de gráficos

Question

¿Alguien sabe si el siguiente problema se ha resuelto o tiene una solución fácil?

Dado un gráfico $(V,E)$ dos subconjuntos de los vértices $U_1=\{u_1, \dots, u_r \}, U_2=\{v_1, \dots, v_s \} \subset V$ y una función $$f: \mathcal{P}(V) \times \mathcal{P}(V) \rightarrow \{0,1\}$$ s.t. $$ f(\{u_1, \dots, u_r \}, \{v_1, \dots, v_s \}) = $$ \begin {casos} 1 & \exists \mbox { cualquier borde entre conjuntos } {u_1, \dots , u_r \N -, \N - v_1, \dots v_s \N - v_s \N - v_s \N - v_s \N - v_s \N -} \\ 0 & \mbox {de lo contrario} \end {casos}

donde $\mathcal{P}(V)$ denota el conjunto de potencias de $V$ .

La pregunta entonces es, ¿cuál es la mejor manera de dividir repetidamente el conjunto $V$ para poder verificar la estructura del grafo (aristas entre vértices) con el mínimo número de llamadas a $f$ .

Nota:

Si $|V| = p$ un límite superior en el problema es trivial $p(p-1)/2$ comprobando cada par de vértices individualmente.

Un límite inferior del problema es $[log_2 p]$ que se deduce considerando un gráfico vacío. Encontrar un recubrimiento de biclices da una forma de comprobar que el grafo está vacío.

[Suponemos que $f(\{v_i\},\{v_i\}) = 1$ ]

Notas:

1) ¿Esto parece estar cerca de ser reformulado como una especie de problema de pesaje?

2) Ya hice la pregunta anteriormente en el sitio de Matemáticas, pero no obtuve ninguna respuesta concluyente.

Editar: Para que quede claro, el número óptimo de llamadas se basará en la estructura del gráfico $(V,E)$ que estamos tratando de verificar. Por ejemplo, el gráfico vacío tiene una solución óptima igual al límite inferior y un gráfico totalmente conectado tiene la del límite superior.

Lo que quiero es una generalización, por ejemplo, una respuesta como "si el gráfico contiene $a$ camarillas de tamaño $b$ un límite superior será $g(a,b)$ ..." que llega al corazón del problema.

Answer 1

Ahora estoy asumiendo que el gráfico $G$ cuya estructura intentamos verificar está etiquetada, y que conocemos la posición exacta de todas las aristas que esperamos encontrar.

Si obtenemos $k$ "sí" responde, entonces no podemos garantizar que $G$ contiene más de $k$ bordes, ya que podemos elegir como máximo $k$ aristas (una por cada grafo bipartito completo consultado) que garanticen que las respuestas a esas preguntas eran "sí". Así que necesitamos al menos $e(G)$ preguntas para verificar que todos los bordes requeridos de $G$ están presentes.

Podemos trabajar más rápido en el complemento: necesitamos exactamente tantas preguntas como grafos bipartitos completos se necesiten para cubrir los no bordes de $G$ . Esto es siempre como máximo $n$ (comprobar las vecindades en el complemento), por lo que verificar la presencia de las aristas requeridas suele llevar más tiempo.

Como la mayoría de los gráficos contienen una fracción positiva de todas las aristas posibles, se necesita $\Theta(n^2)$ consultas para un gráfico elegido al azar en $n$ vértices. De forma más general, el número de aristas en $G$ siempre será el factor limitante hasta que $G$ tiene $o(n)$ bordes, por lo que la respuesta sigue siendo poco emocionante hasta que $G$ es muy escaso.

Las respuestas anteriores se conservan debajo de la línea.

---

Edición: esta respuesta cubre menos terreno que la respuesta en el pregunta original de math.SE .

Dejemos que $G= K_n^-$ sea una camarilla con una arista $xy$ borrado. Entonces, la respuesta a la pregunta "¿hay aristas entre $U_1$ y $U_2$ ?" es "sí" a menos que $U_1 = \{x\}$ y $U_2=\{y\}$ (o viceversa). Por lo tanto, aunque sepamos que nuestro grafo es una camarilla con a lo sumo una arista eliminada, no podemos hacerlo mejor que $\binom n 2$ .