Метод Бейкера

В теоретической информатике метод Бейкера — это метод проектирования схем полиномиального приближения (PTAS) для задач на планарных графах . Он назван в честь Бренды Бейкер , которая объявила о нем на конференции 1983 года и опубликовала его в журнале ACM в 1994 году.

Идея метода Бейкера заключается в том, чтобы разбить граф на слои так, чтобы задача могла быть решена оптимально на каждом слое, а затем объединить решения из каждого слоя разумным образом, что приведет к допустимому решению. Этот метод дал PTAS для следующих задач: изоморфизм подграфа , максимальное независимое множество , минимальное покрытие вершин , минимальное доминирующее множество , минимальное доминирующее множество ребер , максимальное соответствие треугольников и многие другие.

Теория двумерности Эрика Демейна , Федора Фомина, Хаджиагайи и Димитриоса Тиликоса и ее ответвления, упрощающие разложения (Демейн, Хаджиагайи и Каварабаяши (2005),Демейн, Хаджиагайи и Каварабаяши (2011)) обобщают и значительно расширяют применимость техники Бейкера для широкого круга задач на планарных графах и, в более общем смысле, графах, исключающих фиксированный минор , таких как графы ограниченного рода, а также для других классов графов, не замкнутых относительно взятия миноров, таких как 1-планарные графы .

Пример техники

Пример, который мы будем использовать для демонстрации метода Бейкера, — это задача о максимальном весе независимого множества .

Алгоритм

НЕЗАВИСИМЫЙ-НАБОР( , , ) ${\displaystyle G}$ ${\displaystyle w}$ ${\displaystyle \epsilon }$ Выберите произвольную вершину и найдите уровни поиска в ширину для корня в точке : ${\displaystyle r}$  ${\displaystyle k=1/\epsilon }$ ${\displaystyle G}$ ${\displaystyle r}$  ${\displaystyle {\pmod {k}}}$ ${\displaystyle \{V_{0},V_{1},\ldots ,V_{k-1}\}}$ для поиска компонентов после удаления ${\displaystyle \ell =0,\ldots ,k-1}$ ${\displaystyle G_{1}^{\ell },G_{2}^{\ell },\ldots ,}$ ${\displaystyle G}$ ${\displaystyle V_{\ell }}$ для вычисления , максимальный вес независимого набора ${\displaystyle i=1,2,\ldots }$ ${\displaystyle S_{i}^{\ell }}$ ${\displaystyle G_{i}^{\ell }}$  ${\displaystyle S^{\ell }=\cup _{i}S_{i}^{\ell }}$ пусть будет решением максимального веса среди ${\displaystyle S^{\ell ^{*}}}$ ${\displaystyle \{S^{0},S^{1},\ldots ,S^{k-1}\}}$ возвращаться  ${\displaystyle S^{\ell ^{*}}}$

Обратите внимание, что приведенный выше алгоритм осуществим, поскольку каждый из них представляет собой объединение непересекающихся независимых множеств. ${\displaystyle S^{\ell }}$

Динамическое программирование

Динамическое программирование используется, когда мы вычисляем независимое множество с максимальным весом для каждого . Эта динамическая программа работает, поскольку каждый является -внешнепланарным графом . Многие NP-полные задачи можно решить с помощью динамического программирования на -внешнепланарных графах. Метод Бейкера можно интерпретировать как покрытие заданных планарных графов подграфами этого типа, нахождение решения для каждого подграфа с помощью динамического программирования и склеивание решений вместе. ${\displaystyle G_{i}^{\ell }}$ ${\displaystyle G_{i}^{\ell }}$ ${\displaystyle k}$ ${\displaystyle k}$

Ссылки

• Бейкер, Бренда С. (1983), «Аппроксимационные алгоритмы для NP-полных задач на планарных графах (предварительная версия)», 24-й ежегодный симпозиум по основам компьютерной науки, Тусон, Аризона, США, 7–9 ноября 1983 г. , IEEE Computer Society, стр. 265–273, doi :10.1109/SFCS.1983.7
• Бейкер, Бренда С. (1994), «Аппроксимационные алгоритмы для NP-полных задач на планарных графах», Журнал ACM , 41 (1): 153–180, doi : 10.1145/174644.174650 , MR  1369197, S2CID  9706753
• Bodlaender, Hans L. (1988), "Динамическое программирование на графах с ограниченной древовидной шириной", в Lepistö, Timo; Salomaa, Arto (ред.), Automata, Languages ​​and Programming, 15th International Colloquium, ICALP '88, Тампере, Финляндия, 11–15 июля 1988 г., Proceedings , Lecture Notes in Computer Science , т. 317, Springer, стр. 105–118, doi :10.1007/3-540-19488-6_110, hdl : 1874/16258 , ISBN 978-3-540-19488-0
• Demaine, Erik D.; Hajiaghayi, Mohammad Taghi; Kawarabayashi, Ken-ichi (2005), "Теория алгоритмических графовых миноров: декомпозиция, аппроксимация и раскраска", 46-й ежегодный симпозиум IEEE по основам компьютерной науки (FOCS 2005), 23–25 октября 2005 г., Питтсбург, Пенсильвания, США, Труды (PDF) , IEEE Computer Society, стр. 637–646, doi :10.1109/SFCS.2005.14, ISBN 0-7695-2468-0, S2CID  13238254
• Demaine, Erik D.; Hajiaghayi, MohammadTaghi; Kawarabayashi, Ken-ichi (2011), "Разложение контракции в графах без J-минора и алгоритмические приложения", в Fortnow, Lance; Vadhan, Salil P. (ред.), Труды 43-го симпозиума ACM по теории вычислений, STOC 2011, Сан-Хосе, Калифорния, США, 6–8 июня 2011 г. , ACM, стр. 441–450, doi : 10.1145/1993636.1993696, hdl : 1721.1/73855 , ISBN 9781450306911, S2CID  16516718
• Demaine, E .; Hajiaghayi, M.; Nishimura, N.; Ragde, P.; Thilikos, D. (2004), "Алгоритмы аппроксимации для классов графов, исключающие графы с одиночным пересечением как миноры", J. Comput. Syst. Sci. , 69 (2): 166–195, doi : 10.1016/j.jcss.2003.12.001.
• Эппштейн, Д. (2000), «Диаметр и ширина дерева в семействах минорно-замкнутых графов», Algorithmica , 27 (3): 275–291, arXiv : math/9907126v1 , doi : 10.1007/s004530010020, S2CID  3172160.
• Эппштейн, Дэвид (1999), «Изоморфизм подграфов в планарных графах и связанные с ним проблемы», Журнал графовых алгоритмов и приложений , 3 (3): 1–27, doi : 10.7155/jgaa.00014 , MR  1750082, S2CID  2303110
• Григорьев, Александр; Бодлендер, Ханс Л. (2007), «Алгоритмы для графов, встраиваемых с небольшим количеством пересечений на ребро», Algorithmica , 49 (1): 1–11, doi :10.1007/s00453-007-0010-x, hdl : 1874/17980 , MR  2344391, S2CID  8174422.