J. Dreier:

"Lacon- and Shrub-Decompositions: A New Characterization of First-Order Transductions of Bounded Expansion Classes";

Talk: LICS 2021 - Symposium on Logic in Computer Science, Rom; 2021-06-29 - 2021-07-02; in: "Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science", (2021), ISBN: 978-1-6654-4895-6; 1 - 13.

The concept of bounded expansion provides a robust

way to capture sparse graph classes with interesting algorithmic

properties. Most notably, every problem definable in first-order

logic can be solved in linear time on bounded expansion graph

classes. First-order interpretations and transductions of sparse

graph classes lead to more general, dense graph classes that

seem to inherit many of the nice algorithmic properties of their

sparse counterparts.

In this work we introduce lacon- and shrub-decompositions

and use them to characterize transductions of bounded expansion

graph classes and other graph classes. If one can efficiently

compute sparse shrub- or lacon-decompositions of transductions

of bounded expansion classes then one can solve every problem

definable in first-order logic in linear time on these classes.

http://dx.doi.org/10.1109/LICS52264.2021.9470680

https://publik.tuwien.ac.at/files/publik_299558.pdf

Created from the Publication Database of the Vienna University of Technology.