Техника Бейкера
В теоретической информатике метод Бейкера представляет собой метод проектирования аппроксимационных схем с полиномиальным временем (PTAS) для задач на планарных графах . Он назван в честь Бренды Бейкер , которая объявила о нем на конференции 1983 года и опубликовала в Журнале ACM в 1994 году.
Идея метода Бейкера состоит в том, чтобы разбить граф на слои, чтобы задача могла быть решена оптимальным образом на каждом слое, а затем разумным образом объединить решения из каждого слоя, что приведет к допустимому решению. Этот метод дал PTAS для следующих задач: изоморфизм подграфов , максимальное независимое множество , минимальное покрытие вершин , минимальное доминирующее множество , минимальное доминирующее множество ребер , максимальное совпадение треугольников и многие другие.
Теория двумерности Эрика Демена , Федора Фомина, Хаджиагайи и Димитриоса Тиликоса и ее ответвления , упрощающие разложения ( Демен, Хаджиагайи и Каварабаяши (2005) , Демен, Хаджиагайи и Каварабаяши (2011) ) обобщают и значительно расширяют применимость техники Бейкера для обширный набор задач на плоских графах и, в более общем смысле , на графах, исключающих фиксированный минор , таких как графы ограниченных родов, а также на другие классы графов, не замкнутых при взятии миноров, таких как 1-планарные графы .
Пример, который мы будем использовать для демонстрации техники Бейкера, — это задача о независимом множестве максимального веса.
Обратите внимание, что приведенный выше алгоритм реализуем, поскольку каждое из них является объединением непересекающихся независимых множеств.
Динамическое программирование используется, когда мы вычисляем независимый набор максимального веса для каждого . Эта динамическая программа работает, потому что каждый из них является -внепланарным графом . Многие NP-полные задачи можно решить с помощью динамического программирования на -внепланарных графах. Технику Бейкера можно интерпретировать как покрытие заданных плоских графов подграфами этого типа, нахождение решения для каждого подграфа с помощью динамического программирования и склейку решений вместе.
