Problèmes d'optimisation MSOL sur les graphiques de largeur de clique bornée, avec des prédicats de cardinalité

CMSOL est la logique de deuxième ordre monadique, c'est-à-dire une logique de graphiques où le domaine est l'ensemble des sommets et des arêtes, il y a des prédicats pour la contiguïté des sommets et les incidences des arêtes et des sommets, il y a une quantification sur les arêtes, les sommets, les ensembles d'arêtes et les sommets. ensembles, et il existe un prédicat qui exprime si la taille de est modulo . $\textrm{Card}_{n,p}(S)$ $S$ $n$ $p$

Le célèbre théorème de Courcelle déclare que si est une propriété de graphes exprimables en CMSOL, alors pour chaque graphe de largeur d'arbre au plus il peut être décidé en temps linéaire si est , à condition qu'une décomposition arborescente de soit donnée en entrée. Les versions ultérieures du théorème ont supprimé l'exigence qu'une décomposition d'arbre soit donnée en entrée (car on peut être calculé avec l'algorithme de Bodlaender ), et a également permis une optimisation au lieu d'une simple décision; c'est-à-dire, étant donné une formule MSOL nous pouvons également calculer le plus grand ou le plus petit ensemble qui satisfait $\Pi$ $G$ $k$ $\Pi$ $G$ $\phi(S)$ $S$ . $\phi(S)$

Ma question concerne l'adaptation du théorème de Courcelle à des graphes de largeur de clique bornée. Il existe un théorème similaire qui dit que si vous avez un MSOL1 qui permet la quantification sur les sommets, les bords, les ensembles de sommets mais pas les ensembles de bords, alors étant donné un graphique de largeur de clique (avec une expression de clique donnée), pour chaque fixe, il peut être décidé en temps linéaire si le graphe satisfait à une formule MSOL1 ; toutes les références que j'ai vues indiquent $G$ $k$ $k$ $G$ $\phi$

Problèmes d'optimisation soluble dans le temps linéaire sur des graphiques de largeur de clique bornée par Courcelle, Makowsky et Rotics, Theory of Computing Systems, 2000.

J'ai essayé de lire le document, mais il n'est pas autonome par rapport à la définition exacte de MSOL1 et il est franchement difficile à lire. J'ai deux questions concernant ce qui est exactement possible d'optimiser en FPT, paramétré par la largeur de clique du graphe, si une expression de clique est donnée en entrée.

MSOL1 autorise-t-il le prédicat pour tester la taille d'un ensemble modulo un certain nombre? $\textrm{Card}_{n,p}(S)$
Est-il possible de trouver un ensemble de taille minimum / maximum qui satisfait une formule MSOL1 en FPT paramétré par largeur de clique, lorsque l'expression est donnée? $S$ $\phi(S)$

Pour ces deux questions, j'aimerais également savoir quelles sont les bonnes références à citer lorsque je revendique ces résultats. Merci d'avance!

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

J'ai essayé de modifier une partie de votre article, désolé. Parce que je suis assez intéressé par votre question, mais toujours après la modification, je ne suis pas sûr de bien comprendre vos idées. Donc, voulez-vous dire que vous avez besoin de la définition exacte de MSOL1, et de l'existence d'un prédicat et d'un FPT d'un problème d'optimisation?

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$

Les projets de volumes de Bruno Courcelle pourraient être utiles: voir labri.fr/perso/courcell/ActSci.html sous "Structure graphique et logique monadique du second ordre, une approche théorique du langage".

András Salamon,

Merci; cela règle au moins la partie 1) du problème, car son théorème 6.4 dans la première partie du livre dit: Pour tous les ensembles finis K et L des étiquettes de sommet et de bord, le problème de vérification du modèle d'une formule de comptage MSOL1 est fixe- paramètre cubique par rapport au paramètre largeur de clique (G) + taille de la formule.

Bart Jansen,

Réponses:

Après avoir demandé un peu plus, il semble que les réponses aux points 1) et 2) soient toutes les deux OUI. L'optimisation de la cardinalité d'un ensemble est possible dans LinEMSOL (comme mentionné par Martin Lackner); comme on me l'a dit, l'existence des prédicats de cardinalité ne pose aucun problème car ils peuvent être efficacement gérés par des automates d'arbres à états finis, qui devraient suivre (plus explicitement que dans l'article référencé à l'origine) de On parse trees et Myhill-Nerode- des outils de type pour gérer les graphiques de rang-largeur borné .

Bart Jansen
la source

http://www.labri.fr/perso/courcell/Textes1/BC-Makowsky-Rotics(2000).pdf (qui est le document que vous avez mentionné mais une version plus lisible) définit LinEMSOL (définition 10). LinEMSOL permet des problèmes d'optimisation MSO1 et le théorème 4 déclare que ces problèmes sont traitables à paramètres fixes en ce qui concerne la largeur de clique. La réponse à votre deuxième puce / question devrait donc être oui.

Concernant la première puce: Dans "Vertex-minors, monadic second-order logic, and a conjecture by Seese" de Bruno Courcelle et Sang-il Oum, les auteurs écrivent que "Il peut être prouvé qu'aucune formule MS φ (X) ne peut exprimer , dans chaque structure, qu'un ensemble X a même une cardinalité [10] "où [10] =" Courcelle, la logique monadique du second ordre des graphes "

J'espère que cela pourra aider

Martin Lackner
la source

Merci pour la perspicacité, mais le fait qu'aucune formule MS (en général) ne puisse exprimer si un ensemble a même une cardinalité n'est pas vraiment pertinent ici, car la question concerne le langage Counting MSOL qui a des prédicats spéciaux ajoutés qui permettent explicitement de tester la cardinalité d'un ensemble modulo un certain nombre fixe; par conséquent, dans le langage Counting MSOL, il est possible d'exprimer l'uniformité d'un ensemble, et la question était de savoir si nous pouvons trouver efficacement le plus petit / le plus grand ensemble satisfaisant une phrase dans Counting MSOL paramétré par cliquewidth. Merci quand même!

Bart Jansen

Vous avez bien sûr raison. Je voulais juste souligner que le document que vous avez mentionné ne couvre pas CMSOL. (Je ne connais pas de résultat qui fasse ça.)

Martin Lackner