Algoritmo ideal para encontrar a circunferência de um gráfico esparso?

Gostaria de saber como encontrar a circunferência de um gráfico esparso e não direcionado. Por esparso, quero dizer . Por ótimo, quero dizer a menor complexidade de tempo.$|E|=O(|V|)$

Pensei em alguma modificação no algoritmo de Tarjan para gráficos não direcionados, mas não encontrei bons resultados. Na verdade, eu pensei que se eu pudesse encontrar componentes com 2 conexões em , então eu poderia encontrar a circunferência, por algum tipo de indução que pode ser alcançada desde a primeira parte. Eu posso estar no caminho errado, no entanto. Qualquer algoritmo assintoticamente melhor que Θ ( | V | 2 ) (ou seja, o ( | V | 2 ) ) é bem-vindo.$O(|V|)$$\Theta(|V|^2)$$o(|V|^2)$

Aqui está o que eu sei sobre o problema da circunferência em gráficos não ponderados não direcionados. Antes de tudo, se a circunferência é regular, você pode determiná-la em - este é um resultado antigo de Itai e Rodeh (A. Itai e M. Rodeh. Encontrar um circuito mínimo em um gráfico. SIAM J Computing, 7 (4): 413-423, 1978.). A idéia é: para cada vértice no gráfico, inicie um BFS até o primeiro ciclo ser fechado (então pare e vá para o próximo vértice); retorne o ciclo mais curto encontrado. Se a circunferência for mesmo o ciclo mais curto encontrado, será o ciclo mais curto. Em particular, se o seu gráfico for bipartido, isso sempre calculará a circunferência. Se a circunferência g for ímpar, você encontrará um ciclo de comprimento g ou g $O(n^2)$$g$$g$ , então você pode estar desativado por 1 .$g+1$$1$

Agora, o verdadeiro problema com circunferências ímpares é que inevitavelmente seu algoritmo deveria ser capaz de detectar se o gráfico possui um triângulo. Os melhores algoritmos para isso usam multiplicação de matrizes: min { n 2,38 , m 1,41 ) tempo para gráficos em n nós e m arestas. Itai e Rodeh também mostraram que qualquer algoritmo que pode encontrar um triângulo em gráficos densos também pode calcular a circunferência, então temos um algoritmo de circunferência O ( n 2,38 ) . No entanto, o tempo de execução da circunferência em gráficos esparsos não é tão bom quanto para encontrar triângulos. O melhor que sabemos em geral é O ( $O($$n^{2.38}, m^{1.41})$$n$$m$$O(n^{2.38})$ . Em particular, o que parece ser o mais difícil é encontrar umalgoritmo de tempo o ( n 2 ) para gráficos com m = O ( n ) .$O(mn)$$o(n^2)$$m=O(n)$

$2$$n^{1+1/k}$$2k$. Portanto, quanto mais denso o gráfico, mais fácil é encontrar uma boa aproximação à circunferência. Quando o gráfico é muito esparso, a circunferência pode ser essencialmente arbitrariamente grande.

Encontrar circunferência de um gráfico planar tem uma história interessante. Veja este artigo de Chang e Lu para um algoritmo de tempo linear e o histórico de melhorias.

Não existe uma técnica geral para encontrar circunferência de qualquer gráfico esparso. Freqüentemente, precisamos procurar as decomposições ou incorporações especiais associadas para obter melhores limites. Se um gráfico é "comprovadamente" escasso, geralmente há uma boa estrutura associada a ele. Por exemplo, gráficos limitados de largura de árvore são escassos e possuem decomposições de árvore associadas.

$o(n^2)$