Dado um gráfico livre de 4 ciclos

O problema da $k$ ciclo é o seguinte:

Instância: Um gráfico não direcionado $G$ com $n$ vértices e até arestas. $n \choose 2$

Pergunta: Existe um ciclo- (adequado) em ? $k$ $G$

Antecedentes: Para qualquer fixo , podemos resolver ciclo em . $k$ $2k$ $O(n^2)$

Raphael Yuster, Uri Zwick: encontrando ciclos ainda mais rápidos. SIAM J.
Matemática Discreta. 10 (2): 209-222 (1997)

No entanto, não se sabe se podemos resolver os 3 ciclos (ou seja, 3 clique) em menos do que o tempo de multiplicação da matriz.

Minha pergunta: Assumindo que $G$ não contém 4 ciclos, podemos resolver o problema de 3 ciclos em ? $O(n^2)$

David sugeriu uma abordagem para resolver essa variante do problema de 3 ciclos no tempo . $O(n^{2.111})$

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

Parece que, se o menor ciclo de um gráfico

tiver duração de pelo menos 5, ele terá no máximo

G

$G$

bordas. Link:link.springer.com/article/10.1007%2FBF01787638

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

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

Michael Wehar

Informações adicionais podem ser encontradas neste documento: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.94.8121

Michael Wehar

Acho que você também pode estar interessado em Eisenbrand, Friedrich e Fabrizio Grandoni. "Sobre a complexidade do clique do parâmetro fixo e do conjunto dominante." Teórico Computer Science 326.1 (2004): 57-67. (Caso você não estivesse ciente disso).

Juho

Respostas:

Sim, isso é conhecido. Ele aparece em uma das referências obrigatórias sobre a descoberta de triângulos ...

Ou seja, Itai e Rodeh mostram no SICOMP 1978 como encontrar, no tempo , um ciclo em um gráfico que possui no máximo uma borda a mais que o ciclo mínimo de duração. (Veja as três primeiras frases do resumo aqui: http://www.cs.technion.ac.il/~itai/publications/Algorithms/min-circuit.pdf ) É um procedimento simples baseado nas propriedades da largura procurar. $O(n^2)$

Portanto, se o seu gráfico estiver livre de 4 ciclos e houver um triângulo, o algoritmo deles deverá produzi-lo, porque ele não pode produzir um ciclo de 5 ou maior.

Ryan Williams
fonte

$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
fonte

Isso é ótimo! Eu realmente gostei disso. :)

Michael Wehar

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

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

2 k

$2k$

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

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

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

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

O (n^{1.876})

$O(n^{1.876})$

Além disso, para qualquer

k > 2

$k > 2$ , E se

G

$G$ é

2 k

$2k$ -ciclo livre, então podemos determinar se

G

$G$ tem um ciclo de 3 tempos subquadráticos porque

G

$G$ não tem muitas arestas. No entanto, quando

k = 2

$k = 2$ , é aí que as coisas ficam interessantes. Podemos vencer

O (n^{2.111})

$O(n^{2.111})$ ?

Michael Wehar