Histórico e status do problema de correspondência de gráfico

Parte da dificuldade de descobrir mais sobre esse problema é que o problema de correspondência de gráfico é diferente de seu primo muito mais famoso, o problema de correspondência, mas difícil de ser distinguido quando se usa os mecanismos de pesquisa.

Dados dois gráficos e tais que, a tarefa é encontrar uma bijeção modo que essa bijeção estabeleça o máximo possível de correspondências entre as arestas de e .G ′ = ( V ′ , E ′ ) | V | = | V ' | π : V → V ′ G G $G=(V,E)$$G'=(V',E')$$|V| = |V'|$$\pi : V \rightarrow V'$$G$$G'$

Em outras palavras, se e são as matrizes de adjascência, queremos maximizarM $M$$M'$

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

Esse problema contém claramente o isomorfismo do gráfico como um caso especial e pode ser reduzido à correspondência bipartida sob uma redução (não polinomial!).

Que tipo de algoritmos existem e o que se sabe sobre sua complexidade?

Do artigo Isomorfismo de gráfico aproximado :

Estudamos versões de otimização do isomorfismo gráfico. Dados dois gráficos estamos interessados ​​em encontrar uma bijeção de a que maximize o número de correspondências (arestas mapeadas para arestas ou não arestas mapeadas para não arestas). Damos um esquema de aproximação no tempo que, para qualquer fator constante , calcula uma aproximação . Provamos isso combinando o algoritmo de aproximação de erro aditivo de tempo de Arora et al. [Matemática. Program., 92, 2002] com um algoritmo simples de média. Também consideramos o problema de minimização correspondente (de incompatibilidades) e provamos que é NP-difícil$G_1,G_2$$π$V ( G 2 ) n O ( log n ) α < $V(G_1)$$V(G_2)$$n^{O(\log{n})}$$α < 1$$α$$n^{O(\log{n})}$$α$aproximado de para qualquer fator constante . Além disso, mostramos que também é difícil para NP aproximar o número máximo de arestas mapeadas para arestas além de um fator de 0,94.$α$

Não faço ideia do seu problema. Mas, por acaso, conheço uma grande (est) coleção de papéis pertencentes aos algoritmos de correspondência de gráfico COM PDFS . Aplausos para Seth Pettie!

O artigo que @Austin Buchanan apontou acima no Isomorfismo Gráfico aproximado não parece corresponder à versão solicitada. Estou assumindo que a matriz de adjacência possui entradas, caso em que o objetivo está medindo apenas as arestas correspondentes. O modelo aproximado de isomorfismo de gráfico mede as arestas correspondentes e as sem correspondência, o que facilita um pouco do ponto de vista aproximado.$0,1$

Parece que o problema solicitado é pelo menos tão difícil quanto o problema do subgráfico que atualmente admite apenas uma aproximação polinomial. Veja http://arxiv.org/abs/1001.2891 e http://arxiv.org/abs/1110.1360 para obter mais detalhes e o status atual em termos de algoritmos e dureza.$k$

Agora para a redução. Suponha que desejamos resolver o problema do subgráfico em um gráfico ; ou seja, queremos encontrar um subconjunto de nós que maximize o número de arestas no gráfico induzido . Você pode reduzir este para o seu problema, definindo para ser um gráfico que consiste em uma panelinha em -vertices e vértices isolados, e é definido para ser .H k S G [ S ] G k n - k G ′$k$$H$$k$$S$$G[S]$$G$$k$$n-k$$G'$$H$