Максимальный общий индуцированный подграф - Maximum common induced subgraph

В теория графов и теоретическая информатика, а максимальный общий индуцированный подграф двух графиков грамм и ЧАС это граф, который является индуцированный подграф обоих грамм и ЧАС, и имеет как можно больше вершин.

Найти этот график NP-жесткий.В связанном проблема решения, входными данными являются два графика грамм и ЧАС и ряд k. Проблема в том, чтобы решить, грамм и ЧАС имеют общий индуцированный подграф не менее k вершины. Эта проблема НП-полный.^[1] Это обобщение индуцированного проблема изоморфизма подграфов, возникающий при k равно количеству вершин в меньшем из грамм и ЧАС, так что весь этот граф должен появиться как индуцированный подграф другого графа.

На основе твердость приближения результаты для максимальный независимый набор проблема максимального общего индуцированного подграфа также трудно аппроксимировать.^[2] Это означает, что, если только P = NP, здесь нет алгоритм аппроксимации что в полиномиальное время на ${displaystyle n}$-вершинные графы, всегда находит решение с точностью до множителя ${displaystyle n^{1-epsilon }}$ оптимального, для любого ${displaystyle epsilon >0}$.^[3]

Одно из возможных решений этой проблемы - построить модульный граф продукта из грамм и ЧАСНа этом графике наибольшая клика соответствует максимальному общему индуцированному подграфу грамм и ЧАС. Следовательно, алгоритмы поиска максимальных клик можно использовать для поиска максимального общего индуцированного подграфа.^[4]

Алгоритмы максимального общего индуцированного подграфа имеют давнюю традицию в хеминформатика и фармакофорное картирование.^[5]

Смотрите также

• Молекулярная добыча
• Подграф максимального общего ребра

Рекомендации

1. Майкл Р. Гарей и Дэвид С. Джонсон (1979), Компьютеры и непреодолимость: руководство по теории NP-полноты, W.H. Фриман, ISBN  0-7167-1045-5 A1.4: GT48, стр.202.
2. Канн, Вигго (1992), "Об аппроксимируемости проблемы максимального общего подграфа", STACS 92: 9-й ежегодный симпозиум по теоретическим аспектам информатики Кашан, Франция, 13–15 февраля 1992 г., Труды, Конспект лекций по информатике, 577, Springer Science $ mathplus $ Business Media, стр. 375–388, Дои:10.1007/3-540-55210-3_198.
3. Цукерман, Д. (2006), "Линейные экстракторы степени и непроксимируемость максимальной клики и хроматического числа", Proc. 38-й ACM Symp. Теория вычислений, стр. 681–690, Дои:10.1145/1132516.1132612, ISBN  1-59593-134-1, ECCC  TR05-100.
4. Barrow, H .; Берстолл, Р. (1976), «Изоморфизм подграфов, соответствующие реляционные структуры и максимальные клики», Письма об обработке информации, 4 (4): 83–84, Дои:10.1016/0020-0190(76)90049-1.
5. Раймонд, Джон В .; Уиллетт, Питер (2002), «Алгоритмы максимального общего изоморфизма подграфов для сопоставления химических структур» (PDF), Журнал компьютерного молекулярного дизайна, 16 (7): 521–533, Дои:10.1023 / А: 1021271615909.