Paire de cycles disjoints de sommets dans un graphe orienté

13

Quel est l'algorithme déterministe le plus rapide connu qui peut reconnaître des graphes dirigés avec une paire de cycles disjoints de vertex? Je sais que les graphiques avec un minimum de trois degrés ont toujours une telle paire ( Thomassen'83 ), mais même ainsi, je ne trouve pas d'algorithme efficace dans le cas général. Quelqu'un connaît-il une référence pour cela?

reference-request Andreas Björklund
la source
1
Pour les graphes non orientés, il est NP-complet de reconnaître les graphes avec un ensemble de sommets partitionnable en deux cycles disjoints de sommets de taille égale.
Mohammad Al-Turkistany
1
La caractérisation des graphiques non orientés est également non-trivalente, en raison de Lovasz, et peut être trouvée par exemple ici: arxiv.org/abs/1601.03791 .
domotorp

Réponses:

9

knf(k)fk

David Eppstein
la source
2
Je veux juste ajouter un petit commentaire. Il peut être utile d'examiner la largeur d'arbre dirigée et le récent théorème de grille de Kreutzer et Kawarabayashi qui apporte un éclairage supplémentaire sur les techniques dans le papier Reed etal. Ils ont contourné le théorème mineur de la grille dirigée pour prouver le théorème d'Erdos-Posa pour les graphiques dirigés, mais il est utile de voir le schéma de haut niveau à la lumière du théorème de la grille dirigée.
Chandra Chekuri