Das Konzept der Nutzung von Eigenschaften, die ein Diagramm lokal besitzt, kann noch weiter verfolgt werden. Dawar, Grohe und Kreutzer bei lokalem Ausschluss kleinerer Diagrammklassen, bei denen ein kleinerer lokal ausgeschlossen wird, und Dvorak, Kral und Thomas bei der Entscheidung über Eigenschaften erster Ordnung für spärliche Diagramme , bei denen es sich um Diagrammklassen mit (lokal) begrenzter Ausdehnung handelt.
Beide Klassen werden von Klassen nirgendwo dichter Graphen zusammengefasst, die von Nesetril und Ossona de Mendez eingeführt wurden.
Grohe gab diese Woche auf der Highlights-Konferenz bekannt, dass Grohe, Kreutzer und Siebertz. haben bewiesen, dass jede Eigenschaft von Graphen, die in der Logik erster Ordnung definiert werden kann, in nahezu linearer Zeit in nirgendwo dichten Klassen von Graphen gelöst werden kann. Dies impliziert viele Traktabilitätsergebnisse mit festen Parametern für nirgendwo dichte Graphen, z. B. für den (verbundenen) dominierenden Mengen- und Digraphenkern (beide parametrisiert durch die Größe der Lösung), den Steiner-Baum (parametrisiert durch die Größe des Baums) und die Erfüllbarkeit der Schaltung ( parametrisiert durch die Tiefe des Kreislaufs und das Hamming-Gewicht der Lösung).
Sebastian Siebertz
quelle