Two new perspectives on algorithmic meta-theorems : evaluating approximate first-order counting queries on bounded expansion and first-order queries on random graphs

Dreier, Jan; Rossmanith, Peter (Thesis advisor); Siebertz, Sebastian (Thesis advisor)

Aachen (2020, 2021)
Doktorarbeit

Dissertation, RWTH Aachen University, 2020

Kurzfassung

Wir präsentieren zwei algorithmische Meta-Theoreme. Das erste Meta-Theorem ist ein Approximationsschema für das parametrisierte Model-Checking Problem der Zähllogik FO({>0}). Diese Logik erweitert die Prädikatenlogik erster Stufe um die Fähigkeit erfüllende Belegungen einer Variable mit festen, aber beliebig großen Zahlen zu vergleichen. Das Approximationsschema läuft in linearer FPT Zeit (parametrisiert über Formellänge) auf Strukturen mit Bounded Expansion und liefert entweder die korrekte Antwort oder sagt "weiß ich nicht". Letzteres darf nur passieren, wenn kleine Änderungen der Zahlensymbole der Eingabeformel diese auf dem Eingabegraphen erfüllt als auch unerfüllt machen könnten. Unser Ergebnis impliziert, dass jede Eigenschaft, die in FO({>0}) ausgedrückt werden kann, in Linearzeit auf Bounded Expansion Graphklassen approximiert werden kann. Manche Eigenschaften können sogar in Linearzeit exakt gelöst werden. Zum Beispiel erhalten wir einen FPT Algorithmus für Partial Dominating Set auf Bounded Expansion Graphklassen. Andererseits zeigen wir, dass das exakte Lösen des Model-Checking Problems für FO({>0}) schon auf Bäumen beschränkter Tiefe schwer ist, und dass auch das approximative Lösen auf Bäumen schwer wird, falls man die Ausdrucksstärke von FO({>0}) nur leicht erhöht. Unser zweites Meta-Theorem ist ein Model-Checking Algorithmus für Zufallsgraphen und komplexe Netzwerke. Wir sagen ein Zufallsgraphmodell ist alpha-power-law-beschränkt, wenn es (grob gesagt) nicht geclustert ist und der Anteil der Knoten mit Grad k ungefähr O(k^-alpha) ist. Wir lösen das parametrisierte Model-Checking Problem für Prädikatenlogik erster Stufe in erwarteter fast-linearer FPT Zeit auf Zufallsgraphmodellen, die diese Eigenschaft mit alpha >= 3 haben. Dies beinhaltet viele bekannte Modelle komplexer Netzwerke, wie das Preferential Attachment Modell, das Chung-Lu Modell, das Konfigurationsmodell und das Erdős-Rényi Modell. Wir wir zeigen weiterhin, dass das Problem für alpha < 3 nicht mehr in erwarteter FPT Zeit lösbar ist, falls man einem Gegenspieler erlaubt die Knoten des Eingabegraphen zu färben. Unsere Algorithmen basieren auf einer neuen strukturellen Zerlegung von alpha-power-law-beschränkten Zufallsgraphmodellen und neuen Konzentrationsschranken für die Gradentwicklung in Preferential Attachment Graphen.

Einrichtungen

• Fachgruppe Informatik [120000]
• Lehr- und Forschungsgebiet Theoretische Informatik [121220]