Эффективно найти 5-цикл в разреженном графе.

(вставлено из MathOverflow)

Здравствуй,

Я читал эту тему: /mathpro/16393/finding-a-cycle-of-fixed-length

Я хочу найти 5-цикл в графике. На самом деле, то, что я действительно хочу, это кратчайший нечетный цикл длиной не менее 5, но, возможно, это немного не относится к делу. В моих целях я рассматриваю и одинаково в анализе сложности. $m$ $n$

Можем ли мы сделать лучше, чем цветовое кодирование, чтобы найти 5-цикл в этом случае? Позвольте мне дать конкретную формулировку моего вопроса:

Какой минимальный такой, что существует алгоритм времени для обнаружения цикла длиной 5? Какой алгоритм? И что это за если вы запрещаете непрактичные методы, такие как быстрое умножение матриц Копперсмит-Виноград? $\alpha$ $O(m^\alpha)$ $\alpha$

ds.algorithms graph-theory graph-algorithms sparse-matrix Эндрю Д. Кинг
источник

Кросспост из МО.

Сянь-Чи Чанг 之之

У ваших графиков есть какая-то особая структура, кроме того, что они разрежены? (Например, низкое вырождение.)

Робин Котари

Нет, вы можете сделать график настолько дьявольским, насколько захотите. На самом деле меня даже не волнует, является ли график разреженным: я рассматриваю линейный граф и лежащий в его основе граф такой, что (можно считать, что прост). Причина, по которой я лечуито же самое, что я знаюи я хочу проанализировать сложность с точки зренияи, но я не могу ничего сказать о том, каксравнивается с,

G

$G$

H

$H$

G = L (H)

$G=L(H)$

H

$H$

| E (H) |

$|E(H)|$

| V (H) |

$|V(H)|$

| E (H) | = | V (G) |

$|E(H)|=|V(G)|$

| V (G) |

$|V(G)|$

| E (G) |

$|E(G)|$

| E (H) |

$|E(H)|$

| V (H) |

$|V(H)|$

Эндрю Д. Кинг

Чтобы было ясно, вы не возражаете, если цикл содержит повторяющиеся вершины, правильно?

user834

Я не допускаю повторных вершин, но для 5-ти циклов это не имеет значения, потому что я предполагаю, что граф прост и поэтому не имеет 2-х циклов.

Эндрю Д. Кинг

Ответы:

Чтобы добавить к ответу Михая:

Действительно, 5-цикл (и вообще -цикл ) в разреженных графах может быть решен намного быстрее, чем время используя трюк с высокой / низкой степенью. Вам нужно только взглянуть на еще одну статью Алона, Юстера и Цвика: $k$ $O(mn)$

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.101.4120

Например, 5-цикл может быть найден за время , без какой-либо зависимости от умножения матриц. См. Теорему 3.4 вышеупомянутой связанной статьи. $O(m^{1.67})$

Кроме того, хотя не так сложно уменьшить 5-тактное обнаружение до умножения на булеву матрицу (с постоянными факторами), уменьшение в обратном направлении не проявляется в бумаге с цветовым кодированием. Точное сокращение (которое сохраняет сложность времени выполнения) от умножения логической матрицы до 5-тактного обнаружения не известно.

Райан Уильямс
источник

Плотный регистр по существу эквивалентен умножению логической матрицы с помощью цветового кодирования. См. Http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.103.5167&rep=rep1&type=pdf .

$O(mn)$

Михай
источник

Спасибо! Я посмотрю на газету Моньена, когда смогу получить к ней доступ.

Эндрю Д. Кинг