Введение 2
2 Предварительные сведения 5
3 Алгоритм для перечисления всех тропических связных множеств в произвольном графе 12
4 Алгоритм для перечисления всех тропических связных множеств в хордальном графе 16
5 Алгоритм для хордальных графов с небольшой древесной шириной 20
Список использованных источников 25
Разработка эффективных алгоритмов для перечисления всех возможных решений какой-то задачи восходит к 1950-м [1; 2; 3]. Цель перечисляющих алгоритмов - посчитать количество решений или вывести все решения одно за другим. Их изучение началось с задач сложности и оптимизации [4; 5; 6], затем распространилось на другие области, включая биоинформатику, машинное обучение, анализ сетей и социальный анализ [1; 7; 8] . В частности существует много задач на графах, ответ к которым - список подмножеств вершин, обладающих определённым свойством.
Одним из частных случаев задач, для которых разрабатываются перечисляющие алгоритмы - задача ГРАФОВЫЕ УЗОРЫ, введённая в 1994 Моррисом [9] и мотивированная различными приложениями, например, в биологии [10] и расчёте метаболических сетей [11]. Входом задачи является раскрашенный граф (G;с), где количество вершин - п, и M- какое-то мультимножество цветов графа, а c - функция раскраски, не обязательно правильная. Вопросом задачи ставится нахождение такого минимального связного индуцированного подграфа, что цвета вершин подграфа покрывают мультимножество M. В частности представляет интерес случай, когда мультимножество Mопре¬делено как множество всех цветов исходного графа.
Такая задача называется ТРОПИЧЕСКИЕ СВЯЗНЫЕ МНОЖЕСТВА, а искомые подграфы называются тропическими. В работе [12] были получены алгоритмы со временем работы O(1.2721n) для деревьев и O(1.5359n) для произвольных графов, а также для задачи ТРОПИЧЕСКИЕ СВЯЗНЫЕ
МНОЖЕСТВА была показана NP-трудность даже для деревьев высоты 3.
В данной работе рассматриваются алгоритмы для задачи ПЕРЕЧИСЛЕНИЕ ТРОПИЧЕСКИХ Связных МНОЖЕСТВ, в которой надо перечислить все минимальные тропические связные множества (далее MTCS). Эта задача впервые была изучена в статье [13]. В ней были получены нижние оценки количества MTCS и перечисляющие алгоритмы для некоторых видов графов.
В частности для хордального графа была получена только нижняя оценка: был построен граф, в котором количество MTCS превышает 1.4916n. Верхняя оценка на время работы перечисляющего алгоритма осталась тривиальной:
O*(2n).
Хордальные графы определяются как графы, у которых любой цикл, имеющий четыре и более ребра, содержит хорду. Они играют важную роль во многих областях, таких как решение разреженных симметричных систем линейных уравнений [14] и системах управления базами данных [15].
Целью данной работы является построение алгоритмов, работающих быстрее, чем полный перебор. Мы представляем два алгоритма со временем работы O*((2 — ")n) для хордальных и произвольных графов соответственно.
Также был построен алгоритм для хордальных графов, параметризованный таким параметром как древесная ширина графа (treewidth). Этот параметр играет важную роль в разработке многих точных и приближённых алгоритмов для большого количества NP-трудных задач. Понятие treewidth было введено Робертсоном и Сеймуром [16] в своем доказательстве теоремы о минорах графа. Грубо говоря, древесная ширина измеряет похожесть графа на дерево. Например, древесная ширина дерева равна 1. У вышеупомянутого хордального графа с количеством MTCS, превышающем 1.4916n, древесная ширина равна 8, поэтому на алгоритм, полиномиально зависящий от treewidth, надеяться не приходится, но по крайней мере можно построить алгоритм, перечисляющий все MTCS с полиномиальной задержкой.
Результат данной работы
В данной работе получены следующие результаты.
Для задачи ПЕРЕЧИСЛЕНИЕ ТРОПИЧЕСКИХ Связных МНОЖЕСТВ построены алгоритмы со временем работы
1. O*(1.994n) для хордальных графов;
2. O*(1.9999993n) для произвольных графов;
3. O*(max(A, 2tw• 4C•n)) для хордальных графов с древесной шириной tw, количеством цветов Cи количеством MTCS A.
Время работы первых двух построенных алгоритмов даёт верхнюю оценку на количество минимальных тропических связных множеств в произвольных и в хордальных графах. Время работы третьего алгоритма можно рассматривать так: алгоритм перечисляет все MTCS за O* (2tw• 4C• n), если их количество не превышает эту оценку, в противном случае алгоритм перечисляет все MTCS с полиномиальной задержкой.
