Isomorfismo de subgrafo imperfecto

Considere el siguiente problema: dado un gráfico de consulta y un gráfico de referencia , queremos encontrar el mapeo inyectivo que minimiza el número de bordes tal que . Esta es una generalización del problema del isomorfismo del subgrafo en el que permitimos que los subgrafos sean isomorfos hasta algunos bordes faltantes y queremos encontrar la manera de minimizar el número de bordes faltantes. $G = (V, E)$ $G' = (V', E')$ $f : V \rightarrow V'$ $(v_1, v_2) \in E$ $(f(v_1), f(v_2)) \notin E'$

$(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$ está allí para penalizar solo los pesos del gráfico de consulta que es más grande que los del gráfico de referencia).

Mis preguntas son: ¿Ya se ha estudiado este problema? ¿Tiene un nombre conocido? ¿Hay algún algoritmo de aproximación eficiente conocido?

La motivación de este problema (aparte del hecho de que parece una generalización natural del problema de isomorfismo del subgrafo) es que es una buena manera de hacer un plan de mesa para una fiesta: el gráfico de consulta es el gráfico de invitados con pesos de borde representando la medida en que dos personas quieren interactuar, el gráfico de referencia tiene los asientos de la mesa como vértices y pesos de borde que indican hasta qué punto es posible la comunicación, la solución del problema es un mapeo de personas a asientos de mesa que respeta la estructura social para La mayor extensión posible.

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

¿Por qué necesitas "inducido" en el título?

Yota Otachi

@Yota Otachi: Porque me equivoqué. ¡Gracias!

a3nm

Respuestas:

Su problema es el problema del subgrafo de borde común máximo (CES máx.) Definido de la siguiente manera: dados dos gráficos y , encuentre un gráfico con el número máximo de bordes que sea isomorfo a un subgráfico de y a un subgráfico de . $G$ $G'$ $H$ $G$ $G'$

Prueba : está encontrando una subgrafía de isomorfa a una subgrafía de , dondese minimiza Desdees una invariante de , se minimiza si y solo siEstá maximizado. Claramente, es isomorfo a una subgrafía de y a una subgrafía de . QED $H$ $G$ $G'$ $|E_{G}| - |E_{H}|$ $|E_{G}|$ $G$ $|E_{G}| - |E_{H}|$ $|E_{H}|$ $H$ $G$ $G'$

Aproximabilidad En la tesis doctoral de Kann, encontré la descripción "no conocida como aproximable dentro de una constante" [3] (p. 115). En un artículo reciente de Bahiense et al. [1], se menciona que siyno se requiere que sean iguales, el problema se vuelve difícil de APX. Pero la cita para este resultado es una comunicación privada inédita [2]. $|V_{G}|$ $|V_{G'}|$

L. Bahiense, G. Manic, B. Piva, CC de Souza. El problema del subgrafo de borde común máximo: una investigación poliédrica. Matemática aplicada discreta, para aparecer. doi: 10.1016 / j.dam.2012.01.026
MM Halldorsson, Comunicación personal, manuscrito inédito, 1994.
V. Kann. Sobre la aproximabilidad de los problemas de optimización NP-completa. Doctor. Tesis, informe NADA TRITA-NA-9206, 1992. http://www.nada.kth.se/~viggo/papers/phdthesis.pdf

Yota Otachi
fuente

Parece que esto es de hecho equivalente a mi problema. ¡Muchas gracias! ¿Conoce los resultados de una versión ponderada de Max CES?

a3nm

No tengo idea de la versión ponderada. Creo que debería ser , ¿verdad?

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)$

Yota Otachi

Sí, la suma es más natural si queremos generalizar el caso no ponderado, aunque supongo que podría tener sentido minimizar la suma de cuadrados o cualquier función de la diferencia de peso.

a3nm

Gracias por editar Estoy de acuerdo, es natural usar la suma de las diferencias de peso (o cualquier función en él) como penalización.

Yota Otachi