Доброго времени суток! Есть такая задача. Покрыть граф (обыкновенный) k рёберно-непересекающимися деревьями (минимальным количеством деревьев). Она вроде как NP-полна, т.к. свёл к ней рёберную k-раскраску. Сейчас нужно написать по этой задаче какой-нибудь хороший перебор, чтобы было в дальнейшем с чем сверять результаты приближенных методов. В этом-то, собственно, на данный момент и заключается проблема. Думал свести эту задачу к чему-нибудь более известному NP-полному, пока ничего не вышло.
Кроме того, хорошо было бы найти какую-нибудь функцию оценки решения (для использования в методах дискретной оптимизации в дальнейшем), лучшую, чем просто "количество деревьев".
Буду очень благодарен за помощь.
Задача очень интересная, и, честно говоря, мне почему-то кажется, что для случая с двумя деревьями она разрешима за полиномиальное время. Хотелось бы услышать что-то от более знающих людей.
Если имеется ввиду покрытие непересекающимися деревьями, то вроде она разрешима и для N деревьев. Искать по ключевым словам "объединение матродиов".
Для разбиения на два дерева есть даже готовая задачка. Там делается пересечение в принципе, что немного попроще. Три матроида уже плохо пересекаются.
Спасибо за совет, попробую что-нибудь поискать на эту тему. Пока только из теоремы Нэш-Вильямс (http://en.wikipedia.org/wiki/Arboricity) получилось, что в переборе можно рассматривать только подграфы, лежащие в блоках графа. :)
Пересечение трёх матроидов уже NP.
Стоп, для случая двух деревьев тоже NP получается. К ней Not-All-Equal-3SAT сводится.
Для двух есть алгоритм. Делающий что-то с паросочетниями и какими-то хитрыми дополняющими путями. Может у вас редукция неверная?
Вполне вероятно.
Извиняюсь за тупой вопрос, но какие именно матроиды мы должны в этой задаче пересекать?
Носитель — ребра графа. Подмножество хорошее, если оно не содержит циклов. Только надо объединять, а не пересекать. Одно к другому как-то сводится.
Как следует порылся в гугле. Теперь у меня складывается впечатление, что мы тут говорим о разных задачах.
Задача 1: Разбить граф на k рёберно-непересекающихся деревьев. (На минимальное число рёберно-непересекающихся деревьев) NP-полна при k >= 2. При k = 2 через неё решается Not-All-Equal-3SAT. При k > 2 — k-раскраска.
Задача 2: Разбить граф на k остовных лесов, объединение которых даёт исходный граф (Так же найти минимальное k). Решается за полиномиальное время. Предполагается, что решение есть в статье "Forests, frames, and games: Algorithms for matroid sums and applications" Gabow, Harold N.; Westermann, Herbert H. , которую можно преобрести за 5$ — 40$ на соответствующих сайтах
Если я ошибся, и эти задачи эквивалентны, то, судя по всему, P = NP ;)