Dado un gráfico libre de 4 ciclos

El problema $k$ -cycle es el siguiente:

Instancia: un gráfico no dirigido $G$ con $n$ vértices y hasta aristas. $n \choose 2$

Pregunta: ¿Existe un ciclo (adecuado) en ? $k$ $G$

Antecedentes: para cualquier fija , podemos resolver el ciclo en el tiempo . $k$ $2k$ $O(n^2)$

Raphael Yuster, Uri Zwick: Encontrar incluso ciclos incluso más rápido. SIAM J.
Matemáticas discretas. 10 (2): 209-222 (1997)

Sin embargo, no se sabe si podemos resolver 3 ciclos (es decir, 3 camarillas) en menos del tiempo de multiplicación de la matriz.

Mi pregunta: Suponiendo que no contiene 4 ciclos, ¿podemos resolver el problema de 3 ciclos en el tiempo ? $G$ $O(n^2)$

David sugirió un enfoque para resolver esta variante del problema de 3 ciclos en el tiempo . $O(n^{2.111})$

graph-theory graph-algorithms clique polynomial-time fixed-parameter-tractable Michael Wehar
fuente

Parece que si el ciclo más pequeño de un gráfico

tiene una longitud de al menos 5, entonces tiene como máximo

G

$G$

bordes. Enlace:link.springer.com/article/10.1007%2FBF01787638

O (n^{\frac{3}{2}})

$O(n^{\frac{3}{2}})$

Michael Wehar

Se puede encontrar información adicional en este documento: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.94.8121

Michael Wehar

Creo que también te pueden interesar Eisenbrand, Friedrich y Fabrizio Grandoni. "Sobre la complejidad de la camarilla de parámetros fijos y el conjunto dominante". Informática teórica 326.1 (2004): 57-67. (En caso de que aún no lo supieras).

Juho

Respuestas:

Sí, esto se sabe. Aparece en una de las referencias imprescindibles sobre la búsqueda de triángulos ...

A saber, Itai y Rodeh muestran en SICOMP 1978 cómo encontrar, en , un ciclo en un gráfico que tenga como máximo un borde más que el ciclo de longitud mínima. (Vea las primeras tres oraciones del resumen aquí:http://www.cs.technion.ac.il/~itai/publications/Algorithms/min-circuit.pdf) Es un procedimiento simple basado en las propiedades de amplitud primero buscar. $O(n^2)$

Entonces, si su gráfico es libre de 4 ciclos y hay un triángulo, su algoritmo debe generarlo, porque no puede generar un ciclo de 5 ciclos o más.

Ryan Williams
fuente

No es cuadrático, sino Alon Yuster y Zwick ("Encontrar y contar ciclos de longitud dados", Algorithmica 1997) dan un algoritmo para encontrar triángulos en el tiempo , donde es el exponente para el rápido multiplicación de matrices Para los gráficos 4-ciclo-libres, enchufar y (más allí es un -ciclo, independientemente de la existencia de -cycles) da tiempo $O(m^{2\omega/(\omega+1)})$ $\omega$ $\omega<2.373$ $m=O(n^{3/2})$ $4$ $3$ . $O(n^{3\omega/(\omega+1)})=O(n^{2.111})$

David Eppstein
fuente

¡Esto es genial! Realmente lo aprecio. :)

Michael Wehar

Sí, si un gráfico no tiene 4 ciclos, entonces tiene como máximo

bordes. Enlace:books.google.com/…

O (n^{\frac{3}{2}})

$O(n^{\frac{3}{2}})$

Michael Wehar

Siéntete libre de corregirme si me equivoco. Parece que el "Teorema del circuito par" de Erdos dice que si un gráfico está libre de

ciclos, entonces tiene como máximo

2 k

$2k$

bordes. Enlace:sciencedirect.com/science/article/pii/S0012365X99901073

O (n^{1 + \frac{1}{k}})

$O(n^{1+\frac{1}{k}})$

Michael Wehar

Como resultado, si una gráfica no tiene 6 ciclos, entonces tiene como máximo

bordes. Por lo tanto, podemos determinar si tiene un ciclo de 3 ciclos en

usando el método que sugirió David. :)

O (n^{\frac{4}{3}})

$O(n^{\frac{4}{3}})$

O (n^{1.876})

$O(n^{1.876})$

Michael Wehar

Además, para cualquier

fijo , si

k > 2

$k > 2$

G

$G$

libre de ciclo de

, entonces podemos determinar si

tiene un ciclo de 3 ciclos en tiempo subcuadrático porque

no tiene demasiados bordes. Sin embargo, cuando

, es cuando las cosas se ponen interesantes. ¿Podemos vencer a

2 k

$2k$

G

$G$

G

$G$

k = 2

$k = 2$

O (n^{2.111})

$O(n^{2.111})$

Michael Wehar