История и состояние проблемы сопоставления графиков

Часть трудностей, связанных с поиском дополнительной информации об этой проблеме, заключается в том, что проблема сопоставления графов отличается от ее гораздо более известного кузена, проблемы сопоставления, но ее трудно отличить от нее при использовании поисковых систем.

Даны два графа и такие, чтозадача состоит в том, чтобы найти биекцию такую, чтобы эта биекция устанавливала как можно больше соответствий между ребрами и .$G=(V,E)$$G'=(V',E')$$|V| = |V'|$$\pi : V \rightarrow V'$$G$$G'$

Другими словами, если и являются матрицами смежности, то мы хотим максимизировать$M$$M'$

$\sum_{v,w \in V} M_{v,w} \cdot M'_{\pi(v),\pi(w)}$

Эта задача явно содержит изоморфизм графов как частный случай и может быть сведена к двустороннему сопоставлению при (не полиномиальном!) Сокращении.

Какие существуют алгоритмы и что известно о их сложности?

Из статьи Изоморфизм приближенных графов :

Мы изучаем оптимизационные версии графа изоморфизма. Для двух графов нам интересно найти биекцию из в которая максимизирует количество совпадений (ребра, сопоставленные ребрам, или не ребра, сопоставленные не ребрам). Мы даем схему аппроксимации времени , которая для любого постоянного множителя вычисляет аппроксимацию. Мы доказываем это, комбинируя алгоритм приближения времени с аддитивной ошибкой Arora et al. [Math. Program., 92, 2002] с простым алгоритмом усреднения. Мы также рассмотрим соответствующую проблему минимизации (несоответствий) и докажем, что это NP-трудно$G_1,G_2$$π$$V(G_1)$$V(G_2)$$n^{O(\log{n})}$$α < 1$$α$$n^{O(\log{n})}$$α$ -приближенный для любого постоянного фактора . Кроме того, мы показываем, что с точки зрения NP сложно приблизить максимальное количество ребер, отображаемых на ребра, с коэффициентом 0,94.$α$

Я понятия не имею о вашей проблеме. Но мне довелось познакомиться с большим (est) сборником статей, касающихся алгоритмов сопоставления графов с PDFS . Аплодисменты Сету Петти!

Статья, на которую @Austin Buchanan указывал выше о приближенном изоморфизме графа, похоже, не соответствует запрашиваемой версии. Я предполагаю, что матрица смежности имеет записи, и в этом случае целью является измерение только соответствующих ребер. Приближенная модель изоморфизма графа измеряет как совпадающие, так и несопоставленные ребра, что делает ее немного проще с точки зрения приближения.$0,1$

Похоже, что поставленная задача является, по крайней мере, такой же сложной, как и проблема плотного подграфа, которая в настоящее время допускает только полиномиальное приближение. См. Http://arxiv.org/abs/1001.2891 и http://arxiv.org/abs/1110.1360 для получения более подробной информации и текущего состояния с точки зрения алгоритмов и жесткости.$k$

Теперь для сокращения. Предположим, что мы хотим решить проблему плотного подграфа в графе ; то есть мы хотим найти подмножество узлов которое максимизирует количество ребер в индуцированном графе . Вы можете уменьшить это на вашу проблему, установив в графе , состоящий из клика на -vertices и изолированных вершин, и устанавливается равным .$k$$H$$k$$S$$G[S]$$G$$k$$n-k$$G'$$H$