Étant donné un graphe libre

Le problème du $k$ cycle est le suivant:

Instance: Un graphe non orienté $G$ avec $n$ sommets et jusqu'à arêtes. $n \choose 2$

Question: Existe-t-il un (bon) $k$ cycle dans $G$ ?

Contexte: Pour tout fixe $k$ , nous pouvons résoudre un cycle de $2k$ en temps $O(n^2)$ .

Raphael Yuster, Uri Zwick: trouver des cycles pairs encore plus rapides. SIAM J.
Discrete Math. 10 (2): 209-222 (1997)

Cependant, on ne sait pas si nous pouvons résoudre 3 cycles (c'est-à-dire 3-cliques) en moins de temps de multiplication matricielle.

Ma question: en supposant que $G$ ne contient pas de 4 cycles, pouvons-nous résoudre le problème des 3 cycles en temps $O(n^2)$ ?

David a suggéré une approche pour résoudre cette variante du problème à 3 cycles en temps $O(n^{2.111})$ .

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

Il semble que si le plus petit cycle d' un graphe

G

$G$ a une longueur d'au moins 5, alors il a au plus

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

$O(n^{\frac{3}{2}})$ arêtes. Lien: link.springer.com/article/10.1007%2FBF01787638

Michael Wehar

Des informations supplémentaires peuvent être trouvées dans cet article: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.94.8121

Michael Wehar

Je pense que vous pourriez également être intéressé par Eisenbrand, Friedrich et Fabrizio Grandoni. "Sur la complexité de la clique à paramètres fixes et de l'ensemble dominant." Informatique théorique 326.1 (2004): 57-67. (Au cas où vous n'en seriez pas déjà conscient).

Juho

Réponses:

Oui, c'est connu. Il apparaît dans l'une des références incontournables sur la recherche de triangle ...

A savoir, Itai et Rodeh montrent dans SICOMP 1978 comment trouver, en temps , un cycle dans un graphique qui a au plus un bord de plus que le cycle de longueur minimum. (Voir les trois premières phrases du résumé ici: http://www.cs.technion.ac.il/~itai/publications/Algorithms/min-circuit.pdf ) Il s'agit d'une procédure simple basée sur les propriétés de largeur en premier chercher. $O(n^2)$

Donc, si votre graphique est libre sur 4 cycles et qu'il y a un triangle, leur algorithme doit le sortir, car il ne peut pas sortir un 5 cycles ou plus.

Ryan Williams
la source

Ce n'est pas quadratique, mais Alon Yuster et Zwick ("Finding and counting given length cycles", Algorithmica 1997) donnent un algorithme pour trouver des triangles dans le temps , où est l'exposant du rapide multiplication matricielle. Pour les graphes sans-4 cycles, branchent et (sinon il y a un -cycle indépendamment de l' existence de -cycles) donne le temps $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
la source

C'est bien! J'apprécie vraiment cela. :)

Michael Wehar

Oui, si un graphe n'a pas de 4 cycles, alors il a au plus

bords. Lien:books.google.com/…

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

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

Michael Wehar

N'hésitez pas à me corriger si je me trompe. Il semble que "The Even Circuit Theorem" par Erdos dit que si un graphe est sans cycle de

, alors il a au plus

2 k

$2k$

bords. Lien:sciencedirect.com/science/article/pii/S0012365X99901073

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

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

Michael Wehar

Par conséquent, si un graphe n'a pas de cycle 6, alors il a au plus

bords. Par conséquent, nous pouvons déterminer s'il a un temps de 3 cycles en

utilisant la méthode suggérée par David. :)

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

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

O (n^{1.876})

$O(n^{1.876})$

Michael Wehar

De plus, pour tout

fixe , si

est sans cycle de

, alors nous pouvons déterminer si

a un cycle sous-quadratique à 3 cycles parce que

n'a pas trop d'arêtes. Cependant, lorsque

, c'est là que les choses deviennent intéressantes. Peut-on battre

k > 2

$k > 2$

G

$G$

2 k

$2k$

G

$G$

G

$G$

k = 2

$k = 2$

O (n^{2.111})

$O(n^{2.111})$

Michael Wehar