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

9

$k$ $n^{f(k)}$ $f$ $k$

— 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

2

$H$ $G$ $|G|^{f (k+|H|)}$ $k$ $H$ $G$ $|H|=1, k=2$

https://arxiv.org/abs/1603.02504

— Saeed
źródło