Введение
1 Предварительные сведения 17
1.1 Графы 17
1.2 Вычислительная сложность 19
1.3 Выполнимость 19
1.4 Гипотеза экспоненциального времени (ETH) 21
1.5 Задачи с зазором 22
1.6 Формулировки задач
1.6.1 Задачи выполнимости 24
1.6.2 Задачи реберного дополнения 25
2 Наибольший индуцированный хордальный и интервальный подграфы 26
2.1 Используемые леммы 26
2.2 Требуемые свойства 30
2.3 Алгоритм 34
2.4 Описание порядка выбора констант 54
2.5 Заключение 56
Нижние оценки на вычислительную сложность задачи о рёберных дополнениях 58
3.1 Условная нижняя оценка на вычислительную сложность задачи оптимального линейного упорядочивания 58
3.2 Разреженное сведение 68
3.3 Нижние оценки на вычислительную сложность задачи о рёберных дополнениях 82
4 Заключение 90
Литература
