2026-07-22T06:32:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20280 2024-07-02T07:52:55Z ddc:004 open_access

On Classes of Bounded Tree Rank, Their Interpretations, and Efficient Sparsification Gajarský, Jakub McCarty, Rose First-order model checking structural graph theory structural sparsity Graph classes of bounded tree rank were introduced recently in the context of the model checking problem for first-order logic of graphs. These graph classes are a common generalization of graph classes of bounded degree and bounded treedepth, and they are a special case of graph classes of bounded expansion. We introduce a notion of decomposition for these classes and show that these decompositions can be efficiently computed. Also, a natural extension of our decomposition leads to a new characterization and decomposition for graph classes of bounded expansion (and an efficient algorithm computing this decomposition). We then focus on interpretations of graph classes of bounded tree rank. We give a characterization of graph classes interpretable in graph classes of tree rank 2. Importantly, our characterization leads to an efficient sparsification procedure: For any graph class 𝒞 interpretable in a graph class of tree rank at most 2, there is a polynomial time algorithm that to any G ∈ 𝒞 computes a (sparse) graph H from a fixed graph class of tree rank at most 2 such that G = I(H) for a fixed interpretation I. To the best of our knowledge, this is the first efficient "interpretation reversal" result that generalizes the result of Gajarský et al. [LICS 2016], who showed an analogous result for graph classes interpretable in classes of graphs of bounded degree. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jakub Gajarský and Rose McCarty 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.137 urn:nbn:de:0030-drops-202802 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.137 eng https://creativecommons.org/licenses/by/4.0/legalcode