Encontrar triángulos en un gráfico: ¿otros enfoques además de las pruebas de propiedad?

Estamos trabajando en un documento que presenta algunos algoritmos para encontrar triángulos y motivos de red (subgráficos de tamaño constante, también conocidos como grafitos) en un entorno distribuido. Caracterizamos la compensación entre el número de triángulos en el gráfico y la carga de comunicación necesaria. Estoy buscando referencias al trabajo realizado sobre esta cuestión en el modelo centralizado.

El problema es que casi todo lo que encontré sobre este tema que tenía un sabor teórico estaba dentro del marco de las pruebas de propiedad . Para ilustrar la diferencia, considere el caso de un gráfico con vértices, que se compone de triángulos que comparten el borde . Desde el punto de vista de las pruebas de propiedad, este gráfico está muy cerca de estar libre de triángulos (eliminar ese borde crítico hace el trabajo), mientras que tiene un número lineal de triángulos, que es mucho para nuestros estándares. $n$ $n-2$ $\left(1,2\right)$

Cualquier referencia en absoluto será apreciada.

Editar: Me interesan principalmente los algoritmos que pueden determinar si el gráfico contiene triángulos rápidamente. Para los algoritmos de listado de triángulos (u otros subgrafos), el tiempo de ejecución está naturalmente limitado desde abajo por el número de triángulos en el gráfico, ya que el algoritmo necesita enumerarlos a todos, haciendo que tales instancias sean más difíciles en cierto sentido. Desde el punto de vista de un problema de decisión ("sin triángulo o no"), tener muchos triángulos en realidad facilita el problema, ya que puede encontrar fácilmente uno.

reference-request graph-theory graph-algorithms Shir
fuente

Dada la respuesta de David, no estoy seguro de entender más lo que quieres. ¿No le gusta el marco de prueba de propiedad, pero desea límites de complejidad de consulta? ¿Es el ejemplo que da en la pregunta un mal caso porque también desea estimar el número de triángulos?

Suresh Venkat

Esto es lo que quiero: un algoritmo probabilístico que consulta el gráfico y que puede distinguir entre gráficos con muchos triángulos y gráficos sin ninguno. Ver por ejemplo dl.acm.org/citation.cfm?id=1873611 por Gonen, Ron y Shavit. Sin embargo, en su trabajo, la consulta está restringida (por ejemplo, si entiendo correctamente, las consultas de borde no están permitidas, a menos que se muestreen desde una distribución uniforme).

Shir

¿Entonces quieres un algoritmo sublineal que estima el número de triángulos?

Suresh Venkat

algunas observaciones simples: digamos que tiene triángulos T y se le permite la aleatorización; entonces puede muestrear: (1) un borde y golpeará un triángulo con una probabilidad de al menos ~ T ^ {2/3} / m ya que el número mínimo de bordes que puede tener en un gráfico con triángulos T es ~ T ^ {2/3}; una vez que tenga una arista, puede verificar si está en un triángulo en n pasos, para obtener un algoritmo de tiempo de ejecución esperado ~ mn / T ^ {2/3}; (2) puede elegir un triple aleatorio de vértices y con una probabilidad T / n ^ 3 será un triángulo, por lo que obtendrá un tiempo de ejecución de ~ n ^ 3 / T. También puedes hacer algunas cosas un poco más sofisticadas. ¿Esto ayuda?

virgi

Ah, y también, cualquier algoritmo que pueda detectar si un gráfico dado contiene un triángulo en ~ n ^ {3-eps} tiempo puede convertirse en uno que pueda multiplicar nxn matrices booleanas en ~ n ^ {3-eps / 3} tiempo , por eso también son interesantes los algoritmos de detección de triángulos simples y agradables, aunque, por supuesto, las instancias difíciles son cuando necesita distinguir entre los casos de triángulo 0 o 1, y para este caso no sabemos nada mejor que calcular El cubo de la matriz de adyacencia.

virgi

Respuestas:

Para obtener varias referencias sobre el problema de probar la existencia de un triángulo (exactamente, no en el marco de prueba de propiedad), vea el gráfico sin triángulo en Wikipedia. En particular, Alon, Yuster y Zwick (ESA'94) dan un algoritmo O (m ^ {1.41}), y también se puede hacer en un tiempo de multiplicación matricial rápido que es mejor para gráficos densos.

Si está de acuerdo con algo en la configuración de algoritmos de gráficos dinámicos, también tengo uno para contar los triángulos:

El índice h de un gráfico y su aplicación a las estadísticas dinámicas de subgrafos, D. Eppstein y ES Spiro, arXiv: 0904.3741 y WADS 2009.

En nuestro artículo citamos a Chiba y Nishizeki (SICOMP 1985) e Itai y Rodeh (SICOMP 1978) para los hechos básicos del algoritmo estático de que un gráfico con m bordes puede tener como máximo triángulos O (m ^ {3/2}) en el peor de los casos y que se pueden enumerar en ese período de tiempo.

David Eppstein
fuente

Gracias por la rápida respuesta. Ahora veo que no estaba claro en mi pregunta sobre exactamente lo que estamos buscando. Naturalmente, vi las referencias en Wikipedia, pero no encajan del todo, ya que estoy buscando algo en el dominio de la complejidad de la consulta o el tiempo de ejecución de algún algoritmo probabilístico. Editaré la pregunta para reflejar eso. Así que vote por la respuesta, pero no la aceptaré, ya que todavía estoy buscando una respuesta. :)

Shir

En los comentarios a la respuesta de David Eppstein, usted pregunta por el dominio de la complejidad de la consulta. Creo que lo que usted describe no tiene papeles escritos en ella, porque tiene un trivial (determinista o aleatorio) la complejidad consulta límite inferior de (donde es el número de vértices, por lo que se introduce tamaño y, por lo tanto, la complejidad máxima de la consulta). $\Omega(n^2)$ $n$ $O(n^2)$

Si desea ver por qué, considere la siguiente familia de gráficos:

Defina un gráfico como: hay un vértice especial , y dos particiones e de tamaño . Hay un borde entre cada vértice en y y entre cada vértice en y . $G_{0}$ $v$ $X$ $Y$ $(n - 1)/2$ $X$ $v$ $Y$ $v$

Para y defina un gráfico como con el borde agregado. $i \in X$ $j \in Y$ $G_{ij}$ $G_0$ $ij$

no tiene triángulos, y cada tiene 1 triángulo. Dada la promesa de que gráficos es o bien o para algunos y es, obviamente, equivalente a la búsqueda desordenada sobre objetos (los bordes). $G_0$ $G_{ij}$ $G_0$ $G_{ij}$ $i$ $j$ $(n - 1)^2/4$

Artem Kaznatcheev
fuente

Complejidad de consulta WRT, consulte también "Algoritmos cuánticos para el problema del triángulo", Magniez, Santha y Szegedy, SODA'05 y arXiv: quant-ph / 0310134.

David Eppstein

Su ejemplo solo muestra que para el caso de un solo triángulo (supongo que se generaliza fácilmente a O (1)), no caracteriza la compensación entre el número de triángulos y la probabilidad de golpear uno, o insinúa hacia un Buena estrategia de muestreo.

Shir

Θ (n^{2})

$\Theta(n^2)$

Ω (n)

$\Omega(n)$

Ω (\sqrt{N})

$\Omega(\sqrt{N})$

n

$n$

1 - 1 / \sqrt{n}

$1-1/\sqrt{n}$

\sqrt{n}

$\sqrt{n}$

No entiendo exactamente su pregunta en términos de su objetivo final. Sin embargo, podría considerar la versión FPT del problema de empaque triangular, si eso ayuda de alguna manera en su problema. En particular, podría considerar el Empaque de triángulo disjunto de borde (EDTP) o el Empaque de triángulo disjunto de vértice (VDTP) y kernelize la instancia del gráfico a O (k) u O (k ^ 2) respectivamente en términos de número de vértices. También puede kernelize en el número de triángulos [O (k ^ 3)]. Después de la kernelización, sería más fácil analizar los triángulos en la instancia del gráfico.

Nikhil
fuente