Пара вершинных непересекающихся циклов в ориентированном графе

13

Какой самый быстрый известный детерминированный алгоритм может распознавать ориентированные графы с парой вершинных непересекающихся циклов? Я знаю, что графы с минимальной третьей степенью всегда имеют такую пару ( Thomassen'83 ), но даже в этом случае я не могу найти эффективный алгоритм в общем случае. Кто-нибудь знает ссылку на это?

reference-request Андреас Бьёрклунд
источник

1

Для неориентированного графа является NP-полным, чтобы распознавать графы с множеством вершин, разбиваемых на два равноправных вершины непересекающихся циклов.

Мухаммед Аль-Туркистани

1

Характеристика неориентированных графов также нетривиальна из-за Lovasz, и ее можно найти, например, здесь: arxiv.org/abs/1601.03791 .

Domotorp

9

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

Дэвид Эппштейн
источник

2

Просто хочу добавить небольшой комментарий. Возможно, стоит взглянуть на направленную ширину дерева и недавнюю теорему о сетке Крейцера и Каварабаяси, которая проливает некоторый дополнительный свет на методы, описанные в статье Рида-Эталя. Они обошли минорную теорию направленной сетки, чтобы доказать теорему Эрдоса-Посы для ориентированных графов, но полезно взглянуть на схему высокого уровня в свете теоремы о направленной сетке.

Чандра Чекури

2

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

https://arxiv.org/abs/1603.02504

Saeed
источник

Пара вершинных непересекающихся циклов в ориентированном графе

Ответы: