License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2023.132
URN: urn:nbn:de:0030-drops-181848
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18184/
Go to the corresponding LIPIcs Volume Portal

Lampis, Michael

First Order Logic on Pathwidth Revisited Again

pdf-format:
LIPIcs-ICALP-2023-132.pdf (0.8 MB)

Abstract

Courcelle’s celebrated theorem states that all MSO-expressible properties can be decided in linear time on graphs of bounded treewidth. Unfortunately, the hidden constant implied by this theorem is a tower of exponentials whose height increases with each quantifier alternation in the formula. More devastatingly, this cannot be improved, under standard assumptions, even if we consider the much more restricted problem of deciding FO-expressible properties on trees.
In this paper we revisit this well-studied topic and identify a natural special case where the dependence of Courcelle’s theorem can, in fact, be improved. Specifically, we show that all FO-expressible properties can be decided with an elementary dependence on the input formula, if the input graph has bounded pathwidth (rather than treewidth). This is a rare example of treewidth and pathwidth having different complexity behaviors. Our result is also in sharp contrast with MSO logic on graphs of bounded pathwidth, where it is known that the dependence has to be non-elementary, under standard assumptions. Our work builds upon, and generalizes, a corresponding meta-theorem by Gajarský and Hliněný for the more restricted class of graphs of bounded tree-depth.

BibTeX - Entry

@InProceedings{lampis:LIPIcs.ICALP.2023.132,
  author =	{Lampis, Michael},
  title =	{{First Order Logic on Pathwidth Revisited Again}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{132:1--132:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18184},
  URN =		{urn:nbn:de:0030-drops-181848},
  doi =		{10.4230/LIPIcs.ICALP.2023.132},
  annote =	{Keywords: Algorithmic Meta-Theorems, FO logic, Pathwidth}
}

Keywords: Algorithmic Meta-Theorems, FO logic, Pathwidth
Collection: 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Issue Date: 2023
Date of publication: 05.07.2023

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