Problemas de optimización de MSOL en gráficos de ancho de camarilla acotado, con predicados de cardinalidad

CMSOL está contando la lógica monádica de segundo orden, es decir, una lógica de gráficos donde el dominio es el conjunto de vértices y bordes, existen predicados para la adyacencia vértice-vértice y la incidencia de borde-vértice, hay cuantificación sobre bordes, vértices, conjuntos de bordes y vértices establece, y hay un predicado que expresa si el tamaño de es módulo . $\textrm{Card}_{n,p}(S)$ $S$ $n$ $p$

El famoso teorema de Courcelle establece que si es una propiedad de gráficos expresables en CMSOL, entonces para cada gráfico de ancho de árbol como máximo se puede decidir en tiempo lineal si cumple, siempre que se dé una descomposición de árbol de en el entrada. Las versiones posteriores del teorema eliminaron el requisito de que se proporcione una descomposición de árbol en la entrada (porque se puede calcular con el algoritmo de Bodlaender ), y también permitieron la optimización en lugar de la mera decisión; es decir, dada una fórmula MSOL también podemos calcular el conjunto más grande o más pequeño que satisface . $\Pi$ $G$ $k$ $\Pi$ $G$ $\phi(S)$ $S$ $\phi(S)$

Mi pregunta se refiere a la adaptación del teorema de Courcelle a gráficos de ancho de camarilla acotado. Hay un teorema similar que dice que si tiene un MSOL1 que permite la cuantificación sobre vértices, aristas, conjuntos de vértices pero no conjuntos de aristas, entonces se le da un gráfico de ancho de clique (con expresión de clique dada), por cada fijo se puede decidir en tiempo lineal si el gráfico satisface alguna fórmula MSOL1 ; todas las referencias que he visto apuntan a $G$ $k$ $k$ $G$ $\phi$

Problemas de optimización de tiempo lineal solucionable en gráficos de ancho de camarilla acotado por Courcelle, Makowsky y Rotics, Theory of Computing Systems, 2000.

He intentado leer el documento, pero no es autónomo con respecto a la definición exacta de MSOL1 y es francamente difícil de leer. Tengo dos preguntas con respecto a qué es exactamente posible optimizar en FPT, parametrizado por el ancho de clique del gráfico, si se da una expresión de clique en la entrada.

¿MSOL1 permite el para probar el tamaño de un módulo determinado algún número? $\textrm{Card}_{n,p}(S)$
¿Es posible encontrar un conjunto de tamaño mínimo / máximo que satisfaga una fórmula MSOL1 en FPT parametrizada por cliquewidth, cuando se da la expresión? $S$ $\phi(S)$

Para ambas preguntas también me gustaría saber cuáles son las referencias correctas para citar al reclamar estos resultados. ¡Gracias por adelantado!

ds.algorithms reference-request graph-algorithms descriptive-complexity cliquewidth Bart Jansen
fuente

Traté de modificar algunos de sus artículos, lo siento. Porque estoy bastante interesado en su pregunta, pero aún después de la modificación, no estoy seguro si entiendo sus ideas correctamente. Entonces, ¿quiere decir que necesita la definición exacta de MSOL1 y la existencia de un predicado y un FPT de un problema de optimización?

Hsien-Chih Chang 張顯之

Idealmente, lo que me gustaría escuchar es que para cada fórmula fija de , donde es una variable de conjunto de vértices y la fórmula involucra predicados de la Tarjeta , hay un algoritmo que dado un gráfico G y una expresión de camarilla de ancho k, calcula un conjunto de tamaño mínimo que satisface en para alguna función arbitraria (o salidas que ningún conjunto satisface ).

M S O L_{1}

$MSOL_1$

ϕ (S)

$\phi(S)$

S

$S$

ϕ

$\phi$

_{n, p} (S)

$_{n,p}(S)$

S

$S$

ϕ (S)

$\phi(S)$

f (k) | V (G) |^{O (1)}

$f(k) |V(G)|^{O(1)}$

f

$f$

S

$S$

ϕ

$\phi$

Bart Jansen el

Los volúmenes del borrador del libro de Bruno Courcelle pueden ser útiles: consulte labri.fr/perso/courcell/ActSci.html en "Estructura gráfica y lógica monádica de segundo orden, un enfoque teórico del lenguaje".

András Salamon

Gracias; esto al menos resuelve la parte 1) del problema, ya que su Teorema 6.4 en la primera parte del libro dice: Para todos los conjuntos finitos K y L de etiquetas de vértices y bordes, el problema de comprobación de modelo de una fórmula de Counting MSOL1 es fijo. parámetro cúbico con respecto al parámetro cliquewidth (G) + tamaño de la fórmula.

Bart Jansen el

Respuestas:

Después de preguntar un poco más, parece que las respuestas a 1) y 2) son SÍ. La optimización de la cardinalidad de un conjunto es posible en LinEMSOL (como lo menciona Martin Lackner); como me han dicho, la existencia de los predicados de cardinalidad no es un problema, ya que pueden ser manejados eficientemente por autómatas de árboles de estado finito, que deberían seguir (más explícitamente que en el documento originalmente referenciado) de On parse trees y Myhill-Nerode- herramientas de tipo para manejar gráficos de ancho de rango acotado .

Bart Jansen
fuente

http://www.labri.fr/perso/courcell/Textes1/BC-Makowsky-Rotics(2000).pdf (que es el documento que mencionó pero una versión mejor legible) define LinEMSOL (Definición 10). LinEMSOL permite problemas de optimización de MSO1 y el Teorema 4 establece que tales problemas son manejables con parámetros fijos con respecto al ancho de la camarilla. Entonces la respuesta a su segunda viñeta / pregunta debería ser sí.

Con respecto a la primera viñeta: en "Vértice-menores, lógica monádica de segundo orden y una conjetura de Seese" de Bruno Courcelle y Sang-il Oum, los autores escriben que "se puede demostrar que ninguna fórmula de MS φ (X) puede expresar , en cada estructura, que un conjunto X tiene incluso cardinalidad [10] "donde [10] =" Courcelle, la lógica monádica de segundo orden de los gráficos "

Espero que ayude

Martin Lackner
fuente

Gracias por la información, pero el hecho de que ninguna fórmula de MS (en general) pueda expresar si un conjunto tiene incluso cardinalidad no es realmente relevante aquí, ya que la pregunta es sobre el lenguaje Counting MSOL que tiene predicados especiales agregados que permiten explícitamente probar la cardinalidad. de un módulo conjunto algún número fijo; por lo tanto, en el lenguaje Counting MSOL es posible expresar la uniformidad de un conjunto, y la pregunta era si podemos encontrar eficientemente el conjunto más pequeño / más grande que satisfaga una oración en Counting MSOL parametrizada por cliquewidth. ¡Gracias de cualquier manera!

Bart Jansen

Por supuesto que tienes razón. Solo quería señalar que el documento que mencionó no cubre CMSOL. (No sé de un resultado que haga eso.)

Martin Lackner