13.10.2015 Задача реберного дополнения (Иван Близнец)

Мы рассмотрим задачу реберного дополнения до класса графов $\mathcal{G}$. В такой задаче нам на вход задан граф H и целое k, требуется к графу H добавить не более k ребер так, чтобы полученный граф принадлежал классу $\mathcal{G}$. В докладе будут рассмотрены такие классы графов, которые можно охарактеризовать с помощью множества (конечного или бесконечного) запрещенных индуцированных подграфов $\mathcal{F}$. Мы рассмотрим вопросы связанные с нижними оценками на вычислимость, а также приближаемость таких задач.