Encontrar um ciclo de 5 em um gráfico esparso com eficiência.

21

(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. mn

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 O(mα) 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?

Andrew D. King
fonte
3
Crosspost de MO.
Hsien-Chih Chang,
Seus gráficos têm alguma estrutura especial além de esparsa? (Como baixa degeneração, por exemplo).
Robin Kothari
Não, você pode tornar o gráfico tão diabólico quanto quiser. Na verdade, eu nem me importo se o gráfico é escasso: estou considerando um gráfico de linhas , e seu gráfico subjacente modo que (podemos assumir que é simples). A razão de eu tratareo mesmo é que eu seie quero analisar a complexidade em termos dee, mas não posso dizer nada sobre comocompara com. GHG=L(H)H|E(H)||V(H)||E(H)|=|V(G)||V(G)||E(G)||E(H)||V(H)|
Andrew D. King
Para ser claro, você não se importa se o ciclo contém vértices repetidos, correto?
user834
Eu não permito vértices repetidos, mas para um ciclo de 5 não importa, porque eu assumo que o gráfico é simples e, portanto, não tem 2 ciclos.
Andrew D. King

Respostas:

21

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:kO(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.

Ryan Williams
fonte
13

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)

Mihai
fonte
Obrigado! Vou dar uma olhada no artigo de Monien quando tiver acesso a ele.
Andrew D. King