Линейный алгоритм для нахождения числа отдельных замкнутых кривых в ориентированном графе?

Question

Существует ли алгоритм линейного времени для нахождения числа различных замкнутых путей в ориентированном графе?

Достаточно описать псевдокод.

Answer 1

В дальнейшем «цикл» всегда означает «простой цикл» - то есть последовательность вершин, в которой каждая смежная пара вершин связана реброми в исходном графе G, первая и последняя вершины равны , и каждая другая вершина в последовательности появляется не более одного раза.

После некоторого поиска я нашел доказательство того, что эта проблема NP-hard - так никто не знает способа решить ее в линейном времени, никто не знает, как ее решить в polyomial время.

Доказательство, которое я нашел, приведено на с. 2 из http://www.cs.umd.edu/~jkatz/complexity/f11/lecture23.pdf, с которым связано this answer on Quora.

Я перефразировать и расширить на нем немного (я не понимаю, почему они написали «п^п» а «2^(п § п)») здесь:

Пусть у нас есть орграф G, и мы хотим знать, содержит ли G гамильтонов цикл. Мы могли бы решить эту проблему с известными NP-трудностями в полиномиальное время, если бы у вас было многочленное время для вашей задачи (считая число простых циклов в ориентированном графе) следующим образом:

Создайте новый граф G 'из G на беря каждое ребро (u, v) в G и заменяя его «гаджетом», создающим n^n различных путей от u до v. Это можно сделать следующим образом: для каждого ребра (u, v) в G сделать n-by-n сетка n^2 свежих вершин в G ', соединяющая u с каждой из n вершин в первой строке, каждая из этих n вершин в каждую из n вершин в следующей строке (для n^2 всего края первой строки-второй строки), каждая из вершин во второй строке для каждой из вершин третьей строки и т. д. до n-й и последней строки. Подключите каждую вершину в последней строке к v. Через эти вершины мы можем получить от u до v ровно n^n различными способами: на каждой из n строк мы можем выбрать любую из n вершин в этой строке, которая будет включена путь от u до v. Очевидно, что этот гаджет имеет полиномиальный размер (n^2 вершины и (n-1) n^2 + 2n ребер), и нам понадобится не более n^2 его копий (по одному для каждого ребра в G), поэтому G 'тоже. Мы будем кормить этот построенный граф G 'любому алгоритму подсчета направленных циклов в орграфе и использовать ответ, чтобы определить, имеет ли G гамильтонов цикл.

Прежде всего, пусть G имеет гамильтонов цикл. Тогда этот цикл, будучи гамильтонианом, имеет n ребер, поэтому он соответствует в G '(n^n)^n различным циклам, поэтому по крайней мере это много циклов в G'. (Вероятно, будет больше, что соответствует другим циклам, присутствующим в G, но это не имеет значения.)

OTOH, пусть G не имеет гамильтонова цикла. Тогда самый длинный цикл, который он может иметь, имеет длину n-1, а максимальный номер числа циклов, которые он может иметь, ограничено сверху n^(n-1). Чтобы убедиться в этом, заметим, что любой цикл длины не более n-1 можно записать в виде последовательности из n-1 чисел в диапазоне от 1 до n, найдя наименьшую нумерованную вершину в цикле, записав ее и затем записывая каждую последующую вершину в цикле до тех пор, пока исходная вершина не будет достигнута снова, и в этот момент мы могли бы (скажем) продолжать записывать исходное число вершин, пока мы не написали n-1 чисел в целом. Каждый цикл создает отдельный вектор n-1 чисел, и таких векторов не более n^(n-1), поэтому может быть не более n^(n-1) различных циклов в G. С верхними границами на числа и длины циклов в G, теперь мы можем вычислить верхнюю оценку числа циклов в G ': поскольку один цикл в G может иметь не более n-1 ребер, он может производить не более (n^n)^(n-1) циклов в G '; и поскольку в G может быть не более n^(n-1) различных циклов в G, то в G 'может быть не более n^(n-1) * (n^n)^(n-1) циклов.Но это упрощает до n^(n^2-n) * n^(n-1) и оттуда до n^(n^2-1), что явно строго меньше n^(n^2).

Таким образом, мы можем определить, имеет ли G гамильтонов цикл, подавая G 'на алгоритм подсчета циклов в орграфе и глядя на ответ: если он не меньше n^(n^2), то G имеет гамильтониан Цикл, а если он меньше n^(n^2), то G не имеет гамильтонова цикла. Таким образом, если бы существовал алгоритм с многочленом времени для подсчета циклов в орграфе, мы могли бы также решить гамильтоновский цикл (и все остальные NP-полные задачи) в полиномиальное время.