Максимальный цикл в графе

Подскажите пожалуйста алгоритм решения задачи: дан неориентированный граф, нужно найти максимальный цикл в графе.

Какая сложность? Можно back tracking'ом. Больше пока ничего на ум не приходит.

Совершенно очевидно, что это NP-complete задача, ибо если бы за полиномиальное время можно было бы найти максимальный простой цикл, то мы бы автоматически решили бы и TSP (задачу коммивояжера). Просто путем проверки, гамильтонов ли цикл.
Так что про точный алгоритм можно забыть (если конечно P != NP). Лучшее что придумало человечество на сегодняшний день - H.N. Gabow. Finding Paths and Cycles of Superpolylogarithmic Length, In Proceedings of the 36th ACM Symposium on the Theory of Computing (STOC), 2004, 407-416
Но и там циклы далеки от максимальных. Правда время полиномиально

Расшифровывая сказанное выше: перебор, перебор и только полный перебор всех циклов. Приведенная ссылка позволяет оптимизировать перебор, но ценой того, что находятся не самые длинные циклы, а просто "немного длинные"

Цитата shadeofgray @ 25.04.06, 12:29

Расшифровывая сказанное выше: перебор, перебор и только полный перебор всех циклов. Приведенная ссылка позволяет оптимизировать перебор, но ценой того, что находятся не самые длинные циклы, а просто "немного длинные"

Ага, именно так, спасибо :) Я извиняюсь, у меня иногда возникают сложности с объяснением на русском того, что я на русском никогда не изучал...

Цитата kl @ 25.04.06, 11:59

Просто путем проверки, гамильтонов ли цикл.

А при чём здесь гамильтонов цикл? Гамильтонов цикл - это цикл, который проходит через все вершины графа, но не обязательно, что этот цикл максимальный.

Цитата vek21 @ 26.04.06, 06:07

А при чём здесь гамильтонов цикл? Гамильтонов цикл - это цикл, который проходит через все вершины графа, но не обязательно, что этот цикл максимальный.

Скажем, так:
сделаем следующее преобразование графа:
Пусть M --- максимальное ребро. Для каждого ребра (u,v) преобразуем его вес w следующим образом: w'=M-w. Для полученного графа найдем максимальный цикл. Этот же цикл будет являться решением задачи коммивояжера для исходного графа.

Цитата vek21 @ 24.04.06, 20:20

Подскажите пожалуйста алгоритм решения задачи: дан неориентированный граф, нужно найти максимальный цикл в графе.

Если граф эйлеров, то максимальным циклом, не проходящим по ребру дважды в одном направлении, будет эйлеров цикл.

Цитата mo3r @ 26.04.06, 06:55

Гамильтонов цикл - это цикл, который проходит через все вершины графа, но не обязательно, что этот цикл максимальный.

Я, конечно, не спорю, что гамильтонов цикл здесь не при чем, но есть небольшая поправка - гамильтонов цикл всегда минимален для данного графа.

Цитата Arsuit @ 27.04.06, 13:08

Я, конечно, не спорю, что гамильтонов цикл здесь не при чем, но есть небольшая поправка - гамильтонов цикл всегда минимален для данного графа.

Гамильтонов цикл здесь очень даже причем. mo3r достаточно ясно показал, то о чем я говорил в первом посте, а именно, как задача нахождения гамильтонова цикла сводится к исходной задаче. Сводится по Куку. Отсюда автоматически следует, что либо вам удается показать, что P = NP, либо вы не сможете решить свою задачу точно и за приемлемое время. Вот и все.
Любую другую NP-полную задачу тоже можно свести к максимальному циклу. Например поиск максимальной клики в графе, satisfiability, задачу о сумме подпоследовательности и еще пару сотен задач. Но для гамильтонова цикла это показывается наиболее легко.

Цитата Arsuit @ 27.04.06, 13:08

гамильтонов цикл всегда минимален для данного графа.

Это почему?

по опредилению вроде.

Цитата Arsuit @ 06.05.06, 12:31

по опредилению вроде.

Прочитай определение еще разок.

Цитата kl @ 25.04.06, 11:59

Совершенно очевидно, что это NP-complete задача,

Судя по вашим словам, совершенно очевидно, что задача NP=HARD.

Добавлено 07.05.06, 03:36
так на вскидку, я бы сказал что задача скорей всего из класса Р-Space

Да, я согласен, что термин NP-complete тут надо употреблять аккуратнее, потому что он строго определен только для decision problems (а TSP в классической формулировке таковой не является). Тем не менее ее можно перевести в класс decision problems. Но мне не хотелось вдаваться в эти детали, я просто имел в виду, что задача поиска максимального цикла - как минимум так же сложна как и TSP. И наоборот.

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