MSOL-Optimierungsprobleme bei Diagrammen mit begrenzter Gruppenbreite und Kardinalitätsprädikaten

CMSOL zählt die monadische Logik zweiter Ordnung, dh eine Logik von Graphen, bei der die Domäne die Menge von Scheitelpunkten und Kanten ist, es Prädikate für die Scheitelpunkt-Adjazenz und die Scheitelpunkt-Inzidenz gibt, es gibt eine Quantifizierung über Kanten, Scheitelpunkte, Kantensätze und Scheitelpunkte Sätze, und es gibt ein Prädikat , die zum Ausdruck bringt , ob die Größe von ist modulo . $\textrm{Card}_{n,p}(S)$ $S$ $n$ $p$

Courcelles berühmter Satz besagt, dass, wenn eine Eigenschaft von Graphen ist, die in CMSOL ausgedrückt werden können, für jeden Graphen von höchstens in linearer Zeit entschieden werden kann, ob gilt, vorausgesetzt, in der Eingabe ist eine Baumzerlegung von angegeben. In späteren Versionen des Theorems wurde die Anforderung, dass eine Baumzerlegung in der Eingabe angegeben ist (da eine mit dem Bodlaender-Algorithmus berechnet werden kann ), gestrichen und statt einer bloßen Entscheidung auch eine Optimierung zugelassen. dh mit einer MSOL-Formel wir auch die größte oder kleinste Menge berechnen, die erfüllt $\Pi$ $G$ $k$ $\Pi$ $G$ $\phi(S)$ $S$ . $\phi(S)$

Meine Frage betrifft die Anpassung des Courcelle-Theorems an Graphen mit begrenzter Gruppenbreite. Es gibt ein ähnliches Theorem, das besagt, dass wenn Sie eine MSOL1 haben, die eine Quantifizierung über Eckpunkte, Kanten, Scheitelpunktmengen, aber nicht über Kantensätze erlaubt, dann ein Graph der Gruppenbreite (mit gegebenem Gruppenausdruck ) gegeben ist, für jedes feste entschieden werden kann in linearer Zeit, ob der Graph eine MSOL1-Formel erfüllt ; Alle Referenzen, die ich gesehen habe, weisen darauf hin $G$ $k$ $k$ $G$ $\phi$

Lineare zeitlösbare Optimierungsprobleme auf Graphen mit begrenzter Cliquenbreite von Courcelle, Makowsky und Rotics, Theory of Computing Systems, 2000.

Ich habe versucht, das Papier zu lesen, aber es ist in Bezug auf die genaue Definition von MSOL1 nicht in sich geschlossen, und es ist ehrlich gesagt schwer zu lesen. Ich habe zwei Fragen, was genau in FPT optimiert werden kann, parametrisiert durch die Cliquebreite des Graphen, wenn in der Eingabe ein Cliqueausdruck angegeben wird.

Lässt MSOL1 das Prädikat um die Größe einer festgelegten modulo some-Zahl zu testen? $\textrm{Card}_{n,p}(S)$
Ist es möglich, einen minimalen / maximalen Größensatz zu finden, der eine durch die Gruppenbreite parametrisierte MSOL1-Formel in FPT erfüllt, wenn der Ausdruck gegeben ist? $S$ $\phi(S)$

Für diese beiden Fragen möchte ich auch wissen, was die richtigen Referenzen sind, wenn ich diese Ergebnisse beanspruche. Danke im Voraus!

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

Ich habe versucht, einen Teil Ihres Artikels zu ändern. Tut mir leid. Da ich ziemlich an Ihrer Frage interessiert bin, bin ich mir aber nach der Änderung nicht sicher, ob ich Ihre Ideen richtig verstehe. Meinen Sie damit, dass Sie die genaue Definition von MSOL1 und das Vorhandensein von Prädikat und FPT eines Optimierungsproblems benötigen?

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ür einige willkürliche Funktion

(oder Ausgängedass kein Satz

erfüllt

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

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

f

$f$

S

$S$

ϕ

$\phi$

Bart Jansen

Die Heftentwürfe von Bruno Courcelle könnten nützlich sein: siehe labri.fr/perso/courcell/ActSci.html unter " Graphstruktur und monadische Logik zweiter Ordnung, ein sprachtheoretischer Ansatz".

András Salamon

Vielen Dank; Damit ist zumindest Teil 1) des Problems erledigt, da sein Satz 6.4 im ersten Teil des Buches besagt: Für alle endlichen Mengen K und L von Vertex- und Kantenbeschriftungen ist das Modellprüfungsproblem einer Zähl-MSOL1-Formel behoben. Parameter kubisch in Bezug auf den Parameter Gruppenbreite (G) + Größe der Formel.

Bart Jansen

Antworten:

Nach weiteren Fragen scheinen die Antworten zu 1) und 2) beide JA zu sein. Die Optimierung der Kardinalität einer Menge ist in LinEMSOL möglich (wie von Martin Lackner erwähnt); Wie mir bereits gesagt wurde, ist die Existenz der Kardinalitätsprädikate kein Problem, da sie von endlichen Baumautomaten effizient gehandhabt werden können. Typwerkzeuge für die Behandlung von Graphen mit begrenzter Rangbreite .

Bart Jansen
quelle

http://www.labri.fr/perso/courcell/Textes1/BC-Makowsky-Rotics(2000).pdf (das ist das erwähnte Papier, aber eine besser lesbare Version) definiert LinEMSOL (Definition 10). LinEMSOL berücksichtigt MSO1-Optimierungsprobleme, und Theorem 4 besagt, dass solche Probleme hinsichtlich der Clique-Breite über feste Parameter nachvollziehbar sind. Die Antwort auf Ihre zweite Frage sollte also "Ja" lauten.

Zum ersten Punkt: In "Vertex-Minors, monadische Logik zweiter Ordnung und eine Vermutung von Seese" von Bruno Courcelle und Sang-il Oum schreiben die Autoren: "Es kann bewiesen werden, dass keine MS-Formel φ (X) ausdrücken kann in jeder Struktur hat die Menge X eine gerade Kardinalität [10] wobei [10] = "Courcelle, die monadische Logik zweiter Ordnung von Graphen"

Ich hoffe, das hilft

Martin Lackner
quelle

Vielen Dank für die Einsicht, aber die Tatsache, dass keine MS-Formel (im Allgemeinen) ausdrücken kann, ob eine Menge eine gerade Kardinalität hat, ist hier nicht wirklich relevant, da die Frage nach der Counting-MSOL-Sprache besteht, der spezielle Prädikate hinzugefügt wurden, die explizit das Testen der Kardinalität ermöglichen von einer Menge modulo eine feste Zahl; Daher ist es in der Counting MSOL-Sprache möglich, die Gleichheit einer Menge auszudrücken, und die Frage war, ob wir die kleinste / größte Menge effizient finden können, die einem Satz in Counting MSOL entspricht, der durch die Gruppenbreite parametrisiert ist. Danke trotzdem!

Bart Jansen

Sie haben natürlich recht. Ich wollte nur darauf hinweisen, dass das von Ihnen erwähnte Papier nicht CMSOL abdeckt. (Ich weiß nicht von einem Ergebnis, das das tut.)

Martin Lackner