Problemas de otimização do MSOL em gráficos de largura de cliques limitada, com predicados de cardinalidade

CMSOL é Counting Monadic Second Order Logic, ou seja, uma lógica de gráficos em que o domínio é o conjunto de vértices e arestas, existem predicados para adjacência vértice-vértice e incidência de aresta-vértice, quantificação sobre arestas, vértices, conjuntos de arestas e vértices conjuntos, e existe um predicado que expressa se o tamanho de é módulo . $\textrm{Card}_{n,p}(S)$ $S$ $n$ $p$

O famoso teorema de Courcelle afirma que se é uma propriedade de gráficos expressáveis em CMSOL, então para cada gráfico de largura de árvore no máximo pode ser decidido em tempo linear se é válido, desde que uma decomposição de árvore de seja dada na entrada. Versões posteriores do teorema eliminaram o requisito de que uma decomposição em árvore é fornecida na entrada (porque é possível calcular com o algoritmo de Bodlaender ) e também permitia a otimização em vez de apenas a decisão; ou seja, dada uma fórmula MSOL , também podemos calcular o conjunto maior ou menor que satisfaz $\Pi$ $G$ $k$ $\Pi$ $G$ $\phi(S)$ $S$ . $\phi(S)$

Minha pergunta diz respeito à adaptação do teorema de Courcelle a gráficos de largura de cliques limitada. Existe um teorema semelhante dizendo que, se você possui um MSOL1 que permite quantificar sobre vértices, arestas, conjuntos de vértices, mas não conjuntos de arestas, em seguida, é fornecido um gráfico de largura de cliques (com a expressão de clique dada), para cada fixo , pode ser decidido em tempo linear, se o gráfico satisfaz alguma fórmula MSOL1 ; todas as referências que vi apontam para $G$ $k$ $k$ $G$ $\phi$

Problemas lineares de otimização de tempo solucionável em gráficos de largura de clique limitada por Courcelle, Makowsky e Rotics, Teoria de sistemas computacionais, 2000.

Eu tentei ler o artigo, mas ele não é independente com relação à definição exata de MSOL1 e é francamente difícil de ler. Eu tenho duas perguntas sobre o que exatamente é possível otimizar no FPT, parametrizado pela largura de cliques do gráfico, se uma expressão de clique for fornecida na entrada.

$\textrm{Card}_{n,p}(S)$
$S$ $\phi(S)$

Para ambas as perguntas, eu também gostaria de saber quais são as referências corretas ao reivindicar esses resultados. Desde já, obrigado!

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

Tentei modificar parte do seu artigo, desculpe por isso. Porque estou bastante interessado em sua pergunta, mas ainda após a modificação não tenho certeza se entendi suas idéias corretamente. Então, você quer dizer que precisa da definição exata de MSOL1 e da existência de predicado e de um FPT de um problema de otimização?

Hsien-Chih Chang

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$

Os volumes dos rascunhos de Bruno Courcelle podem ser úteis: veja labri.fr/perso/courcell/ActSci.html em "Estrutura de gráfico e lógica monádica de segunda ordem, uma abordagem teórica da linguagem".

András Salamon

Obrigado; isso pelo menos resolve a parte 1) do problema, uma vez que o Teorema 6.4 da primeira parte do livro diz: Para todos os conjuntos finitos K e L de rótulos de vértices e arestas, o problema de verificação de modelo de uma fórmula Counting MSOL1 é fixo. parâmetro cúbico em relação ao parâmetro cliquewidth (G) + tamanho da fórmula.

Bart Jansen

Respostas:

Depois de perguntar um pouco mais, parece que as respostas para 1) e 2) são SIM. A otimização da cardinalidade de um conjunto é possível no LinEMSOL (como mencionado por Martin Lackner); como me disseram, a existência dos predicados de cardinalidade não é um problema, pois eles podem ser eficientemente manipulados por autômatos de árvores de estado finito, que devem seguir (mais explicitamente do que no artigo originalmente mencionado) de On parse trees e Myhill-Nerode- ferramentas de tipo para manipular gráficos de largura de classificação limitada .

Bart Jansen
fonte

http://www.labri.fr/perso/courcell/Textes1/BC-Makowsky-Rotics(2000).pdf (que é o artigo que você mencionou, mas com uma versão mais legível) define LinEMSOL (Definição 10). O LinEMSOL permite problemas de otimização do MSO1 e o Teorema 4 afirma que esses problemas são tratáveis por parâmetros fixos em relação à largura da clique. Portanto, a resposta para o seu segundo marcador / pergunta deve ser sim.

Sobre o primeiro item: Em "Vertex-menores, lógica monádica de segunda ordem e uma conjectura de Seese", de Bruno Courcelle e Sang-il Oum, os autores escrevem que "Pode-se provar que nenhuma fórmula MS φ (X) pode expressar , em toda estrutura, que um conjunto X tem cardinalidade uniforme [10] "onde [10] =" Courcelle, a lógica monádica de segunda ordem dos gráficos "

espero que ajude

Martin Lackner
fonte

Agradecemos a compreensão, mas o fato de nenhuma fórmula MS (em geral) poder expressar se um conjunto tem cardinalidade não é realmente relevante aqui, pois a pergunta é sobre a linguagem Counting MSOL, que inclui predicados especiais que permitem explicitamente testar a cardinalidade de um módulo fixo algum número fixo; portanto, na linguagem Counting MSOL, é possível expressar a uniformidade de um conjunto, e a questão era se podemos encontrar eficientemente o menor / maior conjunto que satisfaz uma sentença no Counting MSOL, parametrizada pela largura de cliques. Obrigado mesmo assim!

Bart Jansen

Claro que você esta certo. Eu só queria enfatizar que o artigo que você mencionou não cobre o CMSOL. (Eu não sei de um resultado que faz isso.)

Martin Lackner