Isomorfismo imperfeito do subgrafo

15

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:VV que minimiza o número de arestas (v1,v2)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(v1),f(v2))E

Eu também estaria interessado na versão ponderada desse problema, onde os pares de vértices carregam um peso w ( v 1 , v 2 ) (que deve ser zero se ( v 1 , v 2 ) E ) , e também para G , e desejamos minimizar v 1 , v 2 ( max ( 0 , w ( v(v1,v2)V2w(v1,v2)(v1,v2)E)G (o máximo existe para penalizar apenas pesos do gráfico de consulta sendo maiores que os do gráfico de referência).v1,v2(max(0,w(v1,v2)w(f(v1),f(v2))))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.

a3nm
fonte
Por que você precisa de "induzido" no título?
Yota Otachi
@Yota Otachi: Porque eu errei. Obrigado!
a3nm 30/05

Respostas:

7

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

Prova : Você está encontrando um subgrafo de G isomórfico em um subgrafo de G , onde | E G | - | E H | é minimizado. Desde | E G | é um invariante de G , | E G | - | E H | é minimizado se e somente se | E H | é maximizado. Claramente, H é isomórfico para um subgrafo de G e para um subgrafo de GHGG|EG||EH||EG|G|EG||EH||EH|HG . QEDG

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 | V G | 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].|VG||VG|

  1. 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
  2. MM Halldorsson, Comunicação pessoal, manuscrito não publicado, 1994.
  3. 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 v 1 , v 2 max ( ) , certo? maxv1,v2max()v1,v2max()
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