¿Existen aplicaciones de descomposición gráfica modular en TCS / teoría de la complejidad?

8

¿Cuáles son algunas aplicaciones de la descomposición gráfica modular en TCS / teoría de la complejidad?

Estoy especialmente interesado en su uso en pruebas o límites superior / inferior si ocurre.

[1] Descomposición gráfica modular , Wikipedia.

[2] Referencias para la descomposición modular , TCS.SE.

reference-request graph-theory graph-algorithms application-of-theory cc.complexity-theory vzn
fuente
2
Habib y Paul hicieron una gran encuesta sobre las aplicaciones algorítmicas de descomposición modular: dx.doi.org/10.1016/j.cosrev.2010.01.001 . Sin embargo, dudo de la aplicabilidad de la descomposición modular en el lado negativo (solo una vista sesgada personal).
Yixin Cao
2
En nuestro resultado reciente que muestra la trazabilidad parametrizada del problema ELIMINACIÓN DE INTERVALOS (para eliminar a lo sumo vértices del gráfico de donaciones para convertirlo en un gráfico de intervalos), la descomposición modular del gráfico desempeña un papel importante. Este problema recibe mucho interés en la comunidad de complejidad parametrizada (aunque no en la comunidad de complejidad tradicional), y los problemas relacionados con las clases de gráficos son los candidatos más naturales de las aplicaciones de descomposición modular de gráficos. k
Yixin Cao
@YixinCao, o ambos, podrían ser respuestas.
Suresh Venkat
La descomposición modular, o al menos la identificación de camarillas homogéneas máximas, es importante para descomponer gráficos sin garras. También me inclino a creer que las descomposiciones modulares no son útiles para los límites inferiores: podemos encontrarlas rápidamente, y una vez que lo hemos hecho, básicamente tenemos una reducción a un gráfico más pequeño. Así que también podemos comenzar con el gráfico más pequeño.
Andrew D. King
1
La tesis doctoral mencionada en esta respuesta muestra enlaces a la teoría de la complejidad descriptiva.
frafl

Respuestas:

11

Habib y Paul hicieron una gran encuesta sobre las aplicaciones algorítmicas de la descomposición modular de gráficos.

k

Sin embargo, no conozco ninguna aplicación de descomposición modular de gráficos en pruebas de límites inferiores, y dudo de su aplicabilidad en el lado negativo (solo una vista sesgada personal).

Un comentario final. Hasta donde yo sé, la mayoría de las aplicaciones algorítmicas no utilizan toda la potencia de la descomposición modular de gráficos. Por ejemplo, las camarillas críticas son los módulos en serie en el segundo nivel de un árbol de descomposición modular (el primer nivel consiste en cada vértice); y los gemelos son módulos (no necesariamente fuertes) formados por dos vértices adyacentes.

Yixin Cao
fuente
gracias. de H&P en línea toc, sec 7, "3 nuevas aplicaciones de la descomposición modular" - coincidencia de patrones / intervalos comunes de dos permutaciones, clasificación genómica / perfecta comparativa por reversiones, complejidad parametrizada y reducciones de kernel / edición de clúster
vzn