Algoritmo óptimo para encontrar la circunferencia de un gráfico disperso?

Me pregunto cómo encontrar la circunferencia de un gráfico escaso no dirigido. Por escaso quiero decir . Por óptimo me refiero a la menor complejidad de tiempo.$|E|=O(|V|)$

Pensé en alguna modificación en el algoritmo de Tarjan para gráficos no dirigidos, pero no encontré buenos resultados. En realidad, pensé que si podía encontrar componentes conectados a 2 en , entonces podría encontrar la circunferencia, mediante algún tipo de inducción que se puede lograr desde la primera parte. Sin embargo, puedo estar en el camino equivocado. Cualquier algoritmo asintóticamente mejor que (es decir, ) es bienvenido.Θ ( | V | 2 ) o ( | V | 2$O(|V|)$$\Theta(|V|^2)$$o(|V|^2)$

Esto es lo que sé sobre el problema de la circunferencia en gráficos no ponderados no dirigidos. En primer lugar, si la circunferencia es pareja, puede determinarla en el tiempo este es un resultado antiguo de Itai y Rodeh (A. Itai y M. Rodeh. Encontrar un circuito mínimo en un gráfico. SIAM J . Computing, 7 (4): 413–423, 1978.). La idea es: para cada vértice en el gráfico, comience un BFS hasta que se cierre el primer ciclo (luego deténgase y pase al siguiente vértice); Devuelve el ciclo más corto encontrado. Si la circunferencia es incluso el ciclo más corto encontrado será el ciclo más corto. En particular, si su gráfico es bipartito, esto siempre calculará la circunferencia. Si la circunferencia g es impar, sin embargo, encontrará un ciclo de longitud g o g $O(n^2)$$g$$g$ , por lo que puede estar apagado por 1 .$g+1$$1$

Ahora, el verdadero problema con la circunferencia impar es que inevitablemente su algoritmo tendría que poder detectar si el gráfico tiene un triángulo. Los mejores algoritmos para eso usan la multiplicación de matrices: min { n 2.38 , m 1.41 ) tiempo para gráficos en$O($$n^{2.38}, m^{1.41})$ nodos ym bordes. Itai y Rodeh también mostraron que cualquier algoritmo que puede encontrar un triángulo en gráficos densos también puede calcular la circunferencia, por lo que tenemos unalgoritmo de circunferencia de tiempo O ( n 2.38 ) . Sin embargo, el tiempo de ejecución para la circunferencia en gráficos dispersos no es tan bueno como para encontrar triángulos. Lo mejor que sabemos en general es O ( $n$$m$$O(n^{2.38})$ . En particular, lo que parece ser lo más difícil es encontrar unalgoritmo de tiempo o ( n 2 ) para gráficos con m = O ( n ) .$O(mn)$$o(n^2)$$m=O(n)$

Si le interesan los algoritmos de aproximación, Liam Roditty y yo tenemos un artículo reciente en SODA'12 sobre eso: Liam Roditty, V. Vassilevska Williams: Algoritmos de aproximación de tiempo subcuadráticos para la circunferencia. SODA 2012: 833-845. Allí mostramos que se puede encontrar una aproximación de en tiempo subcuadrático, y algunos otros resultados relativos a aproximaciones y extensiones aditivas. En términos generales, debido a un teorema de Bondy y Simonovits, cuando tiene gráficos densos, digamos en n 1 + 1 / k bordes, ya contienen ciclos pares cortos, digamos aproximadamente 2 $2$$n^{1+1/k}$$2k$. Entonces, cuanto más denso es el gráfico, más fácil es encontrar una buena aproximación a la circunferencia. Cuando el gráfico es muy escaso, la circunferencia puede ser esencialmente arbitrariamente grande.

Encontrar la circunferencia de un gráfico plano tiene una historia interesante. Consulte este documento de Chang y Lu para obtener un algoritmo de tiempo lineal y el historial de mejoras.

No existe una técnica general para encontrar la circunferencia de ningún gráfico disperso. A menudo tenemos que mirar las descomposiciones especiales o incrustaciones especiales asociadas para lograr mejores límites. Si un gráfico es "demostrablemente" escaso, a menudo hay una bonita estructura asociada a él. Por ejemplo, los gráficos de ancho de árbol acotado son escasos y tienen las descomposiciones de árbol asociadas.

$o(n^2)$