(crossposted from MathOverflow)
Oi,
Eu estava lendo este tópico: /mathpro/16393/finding-a-cycle-of-fixed-length
Eu quero encontrar um ciclo de 5 em um gráfico. Na verdade, o que eu realmente quero é um ciclo ímpar mais curto, de pelo menos 5, mas talvez isso seja um pouco irrelevante. Para meus propósitos, trato e n da mesma forma na análise de complexidade.
Podemos fazer melhor do que o código de cores para encontrar um ciclo de 5 nesse caso? Deixe-me dar uma formulação específica da minha pergunta:
Qual é o \ alpha mínimo que existe um algoritmo de tempo para detectar um ciclo de comprimento 5? Qual é o algoritmo? E o que é isso se você proíbe métodos impraticáveis como a multiplicação rápida de matrizes de Coppersmith-Winograd?
ds.algorithms
graph-theory
graph-algorithms
sparse-matrix
Andrew D. King
fonte
fonte
Respostas:
Para adicionar à resposta de Mihai:
De fato, o ciclo de 5 ciclos (e, em geral, o ciclo ) em gráficos esparsos pode ser resolvido muito mais rápido que o tempo usando o truque de alto / baixo grau. Você precisa apenas olhar para outro artigo de Alon, Yuster e Zwick:k O(mn)
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.101.4120
Por exemplo, um ciclo de 5 pode ser encontrado no tempo , sem nenhuma dependência da multiplicação da matriz. Veja o Teorema 3.4 do documento vinculado acima.O(m1.67)
Além disso, embora não seja muito difícil reduzir a detecção em 5 ciclos à multiplicação da matriz booleana (com sobrecarga de fator constante), uma redução na direção oposta não aparece no papel de código de cores. Não é conhecida uma redução acentuada (que preserva a complexidade do tempo de execução) da multiplicação da matriz booleana para a detecção em 5 ciclos.
fonte
O caso denso é essencialmente equivalente à multiplicação de matrizes booleanas por código de cores. Consulte http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.103.5167&rep=rep1&type=pdf .
Para gráficos esparsos, existe um algoritmo com o tempo devido a [B. Monien, Como encontrar caminhos longos com eficiência, Ann. Discrete Math., 25 (1985), pp. 239-254]. Suspeito que algo melhor possa ser possível com truques de alto ou baixo grau.O(mn)
fonte