License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.126
URN: urn:nbn:de:0030-drops-91300
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9130/
Go to the corresponding LIPIcs Volume Portal

Gajarský, Jakub ; Kreutzer, Stephan ; Nesetril, Jaroslav ; Ossona de Mendez, Patrice ; Pilipczuk, Michal ; Siebertz, Sebastian ; Torunczyk, Szymon

First-Order Interpretations of Bounded Expansion Classes

pdf-format:
LIPIcs-ICALP-2018-126.pdf (0.5 MB)

Abstract

The notion of bounded expansion captures uniform sparsity of graph classes and renders various algorithmic problems that are hard in general tractable. In particular, the model-checking problem for first-order logic is fixed-parameter tractable over such graph classes. With the aim of generalizing such results to dense graphs, we introduce classes of graphs with structurally bounded expansion, defined as first-order interpretations of classes of bounded expansion. As a first step towards their algorithmic treatment, we provide their characterization analogous to the characterization of classes of bounded expansion via low treedepth decompositions, replacing treedepth by its dense analogue called shrubdepth.

BibTeX - Entry

@InProceedings{gajarsk_et_al:LIPIcs:2018:9130,
  author =	{Jakub Gajarsk{\'y} and Stephan Kreutzer and Jaroslav Nesetril and Patrice Ossona de Mendez and Michal Pilipczuk and Sebastian Siebertz and Szymon Torunczyk},
  title =	{{First-Order Interpretations of Bounded Expansion Classes}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{126:1--126:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9130},
  URN =		{urn:nbn:de:0030-drops-91300},
  doi =		{10.4230/LIPIcs.ICALP.2018.126},
  annote =	{Keywords: Logical interpretations/transductions, structurally sparse graphs, bounded expansion}
}

Keywords: Logical interpretations/transductions, structurally sparse graphs, bounded expansion
Collection: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue Date: 2018
Date of publication: 04.07.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI