You are not logged in | Log in

Speaker(s): Szymon Toruńczyk
Affiliation: Uniwersytet Warszawski
Date: June 6, 2018, 2:15 p.m.
Room: room 5050
Title in Polish: Dynamic Enumeration for First-Order Queries on Classes of Bounded Expansion
Seminar: Seminar Automata Theory

Classes of bounded expansion, introduced by Nesetril and Ossona de Mendez,

are sparse graph classes encompassing classes of planar graphs,

classes with bounded maximal degree, classes of bounded treewidth,

or more generally, any class of graphs that excludes a fixed topological minor.

Since the work of Dvorak, Kral and Thomas (2010) it is known that every fixed

first-order sentence can be verified in linear time on a given a graph

from a fixed class of bounded expansion. We revisit this result, presenting its

streamlined proof, and discuss its extension, in the setting of query enumeration

and dynamic updates. Given a graph from the fixed class and a formula,

one can compute, in time linear in the graph size, a data structure that allows to enumerate

the set of tuples satisfying the formula with constant delay between the outputs.

Furthermore, the data structure allows to perform certain alterations of the underlying

graph in constant time, each time resetting the enumeration process.

Joint work with Michał Pilipczuk.

Joint work with Michał Pilipczuk