Несовершенный изоморфизм подграфа

Рассмотрим следующую проблему: учитывая граф запросов $G = (V, E)$ и опорный граф , мы хотим найти инъективное отображение которое минимизирует количество ребра такие, что . Это обобщение проблемы изоморфизма подграфа, где мы позволяем подграфам быть изоморфными вплоть до нескольких отсутствующих ребер и хотим найти способ минимизировать количество отсутствующих ребер.f : V → V ′ ( ( f ( v 1 ) , f ( v 2 ) ) ∉ E $G' = (V', E')$$f : V \rightarrow V'$$(v_1, v_2) \in E$$(f(v_1), f(v_2)) \notin E'$

Я также был бы заинтересован в взвешенной версии этой задачи, где пары вершин несут вес (который должен быть равен нулю, если и аналогично для , и мы хотим минимизировать ( \ max нужно ли штрафовать только веса из графа запросов, которые больше, чем у эталонного графа).$(v_1, v_2) \in V^2$$w(v_1, v_2)$$(v_1, v_2) \notin E)$$G'$$\sum_{v_1, v_2} (\max(0, w(v_1, v_2) - w(f(v_1), f(v_2))))$$\max$

Мой вопрос: эта проблема уже изучена? У него есть известное имя? Известны ли эффективные алгоритмы аппроксимации?

Мотивация этой проблемы (помимо того, что она кажется естественным обобщением проблемы изоморфизма подграфа) заключается в том, что это хороший способ составить план стола для вечеринки: граф запросов - это граф гостей с весами ребер представляющий степень, в которой хотят взаимодействовать два человека, на контрольном графике места в таблице представлены в виде вершин и весов ребер, указывающих, в какой степени возможна связь, решение проблемы заключается в сопоставлении людей с местами за столом, которое учитывает социальную структуру и в максимально возможной степени.

Ваша задача - Задача максимального общего краевого подграфа (Max CES), определяемая следующим образом: для двух графов и найдите граф с максимальным числом ребер, изоморфным подграфу и подграфу .G ′ H G G $G$$G'$$H$$G$$G'$

Доказательство : Вы найти подграф из G , изоморфного подграфа G ' , где | E G | - | E H | сводится к минимуму Так как | E G | является инвариантом группы G , | E G | - | E H | минимизируется тогда и только тогда, когда | E H | максимально Ясно, что H изоморфна подграфу G и подграфу $H$$G$$G'$$|E_{G}| - |E_{H}|$$|E_{G}|$$G$$|E_{G}| - |E_{H}|$$|E_{H}|$$H$$G$ . QED$G'$

Аппроксимируемость. В докторской диссертации Канна я обнаружил описание «неизвестно, что оно аппроксимируется в пределах константы» [3] (с. 115). В недавней статье Bahiense et al. [1], упоминается, что если и | V G ′ | не обязаны быть равными, проблема становится APX-трудной. Но цитата для этого результата - неопубликованное личное сообщение [2].$|V_{G}|$$|V_{G'}|$

1. Л. Баиенсе, Г. Маник, Б. Пива, СиСи де Соуза. Задача о подграфе максимального общего ребра: многогранное исследование. Дискретная прикладная математика, чтобы появиться. DOI: 10.1016 / j.dam.2012.01.026
2. М. М. Халлдорссон, Личное общение, неопубликованная рукопись, 1994.
3. В. Канн. Об аппроксимируемости NP-полных задач оптимизации. Кандидат наук. Дипломная работа, отчет NADA TRITA-NA-9206, 1992. http://www.nada.kth.se/~viggo/papers/phdthesis.pdf