Isomorfismo imperfeito do subgrafo

Considere o seguinte problema: Dado um gráfico de consulta $G = (V, E)$ e um gráfico de referência $G' = (V', E')$ , queremos encontrar o mapeamento injetivo $f : V \rightarrow V'$ que minimiza o número de arestas $(v_1, v_2) \in E$ tal que . Essa é uma generalização doproblema de isomorfismodosubgráfico,em que permitimos que os subgráficos sejam isomórficos até algumas arestas ausentes e queremos encontrar uma maneira de minimizar o número de arestas ausentes. $(f(v_1), f(v_2)) \notin E'$

Eu também estaria interessado na versão ponderada desse problema, onde os pares de vértices carregam um peso (que deve ser zero se , e também para , e desejamos minimizar $(v_1, v_2) \in V^2$ $w(v_1, v_2)$ $(v_1, v_2) \notin E)$ $G'$ (o existe para penalizar apenas pesos do gráfico de consulta sendo maiores que os do gráfico de referência). $\sum_{v_1, v_2} (\max(0, w(v_1, v_2) - w(f(v_1), f(v_2))))$ $\max$

Minha pergunta é: esse problema já foi estudado? Tem um nome conhecido? Existem algoritmos de aproximação eficientes conhecidos?

A motivação desse problema (além do fato de parecer uma generalização natural do problema de isomorfismo do subgráfico) é que é uma boa maneira de fazer um plano de tabela para uma festa: o gráfico de consulta é o gráfico de convidados com pesos de borda representando a extensão em que duas pessoas desejam interagir, o gráfico de referência possui os assentos da mesa como vértices e pesos das arestas, indicando até que ponto a comunicação é possível; a solução do problema é um mapeamento de pessoas para assentos da mesa que respeite a estrutura social o máximo possível.

cc.complexity-theory ds.algorithms graph-theory approximation-algorithms graph-isomorphism a3nm
fonte

Por que você precisa de "induzido" no título?

Yota Otachi

@Yota Otachi: Porque eu errei. Obrigado!

a3nm 30/05

Respostas:

Seu problema é o Máximo problema de subgrafo comum de aresta (Max CES) definido da seguinte forma: dados dois gráficos e , encontre um gráfico com o número máximo de arestas isomórficas para um subgrafo de e para um subgrafo de . $G$ $G'$ $H$ $G$ $G'$

Prova : Você está encontrando um subgrafo de isomórfico em um subgrafo de , onde é minimizado. Desde é um invariante de , é minimizado se e somente se é maximizado. Claramente, é isomórfico para um subgrafo de e para um subgrafo de $H$ $G$ $G'$ $|E_{G}| - |E_{H}|$ $|E_{G}|$ $G$ $|E_{G}| - |E_{H}|$ $|E_{H}|$ $H$ $G$ . QED $G'$

Aproximabilidade. Na tese de doutorado de Kann, encontrei a descrição "não conhecida por ser aproximada em uma constante" [3] (p. 115). Em artigo recente de Bahiense et al. [1], é mencionado que se e não precisa ser igual, o problema se torna difícil para o APX. Mas a citação para este resultado é uma comunicação privada não publicada [2]. $|V_{G}|$ $|V_{G'}|$

L. Bahiense, G. Manic, B. Piva, CC de Souza. O problema máximo do subgráfico da aresta comum: uma investigação poliédrica. Matemática Aplicada Discreta, para aparecer. doi: 10.1016 / j.dam.2012.01.026
MM Halldorsson, Comunicação pessoal, manuscrito não publicado, 1994.
V. Kann. Sobre a aproximabilidade de problemas de otimização NP-complete. Ph.D. Tese, relatório da NADA TRITA-NA-9206, 1992. http://www.nada.kth.se/~viggo/papers/phdthesis.pdf

Yota Otachi
fonte

Parece que isso é realmente equivalente ao meu problema. Muito obrigado! Você está ciente dos resultados de uma versão ponderada do Max CES?

a3nm

Não faço ideia da versão ponderada. Eu acho que

deve ser

, certo?

max_{v_{1}, v_{2}} max (\dots)

$\max_{v_1,v_2} \max (\ldots)$

\sum_{v_{1}, v_{2}} max (\dots)

$\sum_{v_1,v_2} \max (\ldots)$

usar o seguinte código

Sim, a soma é mais natural se quisermos generalizar o caso não ponderado, embora eu ache que possa fazer sentido minimizar a soma dos quadrados ou qualquer função da diferença de peso.

a3nm

Obrigado pela edição. Concordo que é natural usar a soma das diferenças de peso (ou qualquer outra função) como penalidade.

Yota Otachi