Paar von Scheitelpunkt-disjunkten Zyklen in einem gerichteten Graphen

13

Was ist der schnellste bekannte deterministische Algorithmus, der gerichtete Graphen mit einem Paar von Scheitelpunkt-disjunkten Zyklen erkennen kann? Ich weiß, dass Graphen mit mindestens drei Grad immer ein solches Paar haben ( Thomassen'83 ), aber trotzdem kann ich im allgemeinen Fall keinen effizienten Algorithmus finden. Kennt jemand eine Referenz dafür?

reference-request Andreas Björklund
quelle
1
Für ungerichtete Graphen ist es NP-vollständig, Graphen mit einer Scheitelpunktmenge zu erkennen, die in zwei gleich große Scheitelpunkt-Disjunkt-Zyklen unterteilt werden kann.
Mohammad Al-Turkistany
1
Die Charakterisierung für ungerichtete Graphen ist aufgrund von Lovasz ebenfalls nicht trival und kann zB hier gefunden werden: arxiv.org/abs/1601.03791 .
Domotorp

Antworten:

9

Nach Grohe und Grüber " Parametrisierte Approximierbarkeit des Disjunktionszyklusproblems " (ICALP 2007) gibt es einen Algorithmus zum Auffinden von vertexdisjunkten Zyklen in einem Digraphen in der Zeit für eine Funktion (Polynom für festes aber nicht FPT) in Abschnitt 5 von Reed, Robertson, Seymour und Thomas, " Packing directed circuit " (Combinatorica 1996) (der seinerseits Satz 3 von " The directed subgraph hemeomorphism problem " von Fortune, Hopcroft und Wyllie verwendet .)knf(k)fk

David Eppstein
quelle
2
Ich möchte nur einen kleinen Kommentar hinzufügen. Es mag sich lohnen, die gerichtete Baumbreite und den jüngsten Rastersatz von Kreutzer und Kawarabayashi zu betrachten, der zusätzliche Aufschluss über die Techniken in Reed et al. Sie haben sich um den Satz des gerichteten Gitters gekümmert, um den Satz von Erdos-Posa für gerichtete Graphen zu beweisen, aber es ist nützlich, das Schema auf hoher Ebene im Lichte des Satzes des gerichteten Gitters zu sehen.
Chandra Chekuri