Para cykli rozłącznych wierzchołków na ukierunkowanym wykresie

13

Jaki jest najszybszy znany algorytm deterministyczny, który może rozpoznawać skierowane wykresy za pomocą pary rozłącznych cykli wierzchołków? Wiem, że wykresy z min. Min. Trzech zawsze mają taką parę ( Thomassen'83 ), ale mimo to nie mogę znaleźć skutecznego algorytmu w ogólnym przypadku. Czy ktoś zna odniesienia do tego?

reference-request Andreas Björklund
źródło
1
W przypadku wykresów bezkierunkowych rozpoznawanie wykresów z zestawem wierzchołków podzielnym na dwa rozłączne cykle równej wielkości jest NP-zupełne.
Mohammad Al-Turkistany
1
Charakterystyka grafów bezkierunkowych jest również nietrywialna ze względu na Lovasz i można ją znaleźć np. Tutaj: arxiv.org/abs/1601.03791 .
domotorp

Odpowiedzi:

9

knf(k)fk

David Eppstein
źródło
2
Chcę tylko dodać mały komentarz. Warto spojrzeć na ukierunkowaną szerokość i ostatnie twierdzenie siatki Kreutzera i Kawarabayashi, które rzuca dodatkowe światło na techniki przedstawione w pracy Reeda etala. Obeszli małe twierdzenie o ukierunkowanej siatce, aby udowodnić twierdzenie Erdosa-Posa dla grafów ukierunkowanych, ale warto zobaczyć schemat wysokiego poziomu w świetle twierdzenia o ukierunkowanej siatce.
Chandra Chekuri