Search Results

Documents authored by Gajarský, Jakub

Found 2 Possible Name Variants:

Gajarsky, Jakub

Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2024.137
On Classes of Bounded Tree Rank, Their Interpretations, and Efficient Sparsification

Authors: Jakub Gajarský and Rose McCarty

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
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.
Cite as

Jakub Gajarský and Rose McCarty. On Classes of Bounded Tree Rank, Their Interpretations, and Efficient Sparsification. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 137:1-137:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gajarsky_et_al:LIPIcs.ICALP.2024.137,
  author =	{Gajarsk\'{y}, Jakub and McCarty, Rose},
  title =	{{On Classes of Bounded Tree Rank, Their Interpretations, and Efficient Sparsification}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{137:1--137:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.137},
  URN =		{urn:nbn:de:0030-drops-202802},
  doi =		{10.4230/LIPIcs.ICALP.2024.137},
  annote =	{Keywords: First-order model checking, structural graph theory, structural sparsity}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.11
Sparse Graphs of Twin-Width 2 Have Bounded Tree-Width

Authors: Benjamin Bergougnoux, Jakub Gajarský, Grzegorz Guśpiel, Petr Hliněný, Filip Pokrývka, and Marek Sokołowski

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
Twin-width is a structural width parameter introduced by Bonnet, Kim, Thomassé and Watrigant [FOCS 2020]. Very briefly, its essence is a gradual reduction (a contraction sequence) of the given graph down to a single vertex while maintaining limited difference of neighbourhoods of the vertices, and it can be seen as widely generalizing several other traditional structural parameters. Having such a sequence at hand allows to solve many otherwise hard problems efficiently. Our paper focuses on a comparison of twin-width to the more traditional tree-width on sparse graphs. Namely, we prove that if a graph G of twin-width at most 2 contains no K_{t,t} subgraph for some integer t, then the tree-width of G is bounded by a polynomial function of t. As a consequence, for any sparse graph class C we obtain a polynomial time algorithm which for any input graph G ∈ C either outputs a contraction sequence of width at most c (where c depends only on C), or correctly outputs that G has twin-width more than 2. On the other hand, we present an easy example of a graph class of twin-width 3 with unbounded tree-width, showing that our result cannot be extended to higher values of twin-width.
Cite as

Benjamin Bergougnoux, Jakub Gajarský, Grzegorz Guśpiel, Petr Hliněný, Filip Pokrývka, and Marek Sokołowski. Sparse Graphs of Twin-Width 2 Have Bounded Tree-Width. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 11:1-11:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bergougnoux_et_al:LIPIcs.ISAAC.2023.11,
  author =	{Bergougnoux, Benjamin and Gajarsk\'{y}, Jakub and Gu\'{s}piel, Grzegorz and Hlin\v{e}n\'{y}, Petr and Pokr\'{y}vka, Filip and Soko{\l}owski, Marek},
  title =	{{Sparse Graphs of Twin-Width 2 Have Bounded Tree-Width}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{11:1--11:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.11},
  URN =		{urn:nbn:de:0030-drops-193130},
  doi =		{10.4230/LIPIcs.ISAAC.2023.11},
  annote =	{Keywords: twin-width, tree-width, excluded grid, sparsity}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2023.128
Flipper Games for Monadically Stable Graph Classes

Authors: Jakub Gajarský, Nikolas Mählmann, Rose McCarty, Pierre Ohlmann, Michał Pilipczuk, Wojciech Przybyszewski, Sebastian Siebertz, Marek Sokołowski, and Szymon Toruńczyk

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
A class of graphs C is monadically stable if for every unary expansion Ĉ of C, one cannot encode - using first-order transductions - arbitrarily long linear orders in graphs from C. It is known that nowhere dense graph classes are monadically stable; these include classes of bounded maximum degree and classes that exclude a fixed topological minor. On the other hand, monadic stability is a property expressed in purely model-theoretic terms that is also suited for capturing structure in dense graphs. In this work we provide a characterization of monadic stability in terms of the Flipper game: a game on a graph played by Flipper, who in each round can complement the edge relation between any pair of vertex subsets, and Localizer, who in each round is forced to restrict the game to a ball of bounded radius. This is an analog of the Splitter game, which characterizes nowhere dense classes of graphs (Grohe, Kreutzer, and Siebertz, J. ACM '17). We give two different proofs of our main result. The first proof is based on tools borrowed from model theory, and it exposes an additional property of monadically stable graph classes that is close in spirit to definability of types. Also, as a byproduct, we show that monadic stability for graph classes coincides with monadic stability of existential formulas with two free variables, and we provide another combinatorial characterization of monadic stability via forbidden patterns. The second proof relies on the recently introduced notion of flip-flatness (Dreier, Mählmann, Siebertz, and Toruńczyk, arXiv 2206.13765) and provides an efficient algorithm to compute Flipper’s moves in a winning strategy.
Cite as

Jakub Gajarský, Nikolas Mählmann, Rose McCarty, Pierre Ohlmann, Michał Pilipczuk, Wojciech Przybyszewski, Sebastian Siebertz, Marek Sokołowski, and Szymon Toruńczyk. Flipper Games for Monadically Stable Graph Classes. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 128:1-128:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gajarsky_et_al:LIPIcs.ICALP.2023.128,
  author =	{Gajarsk\'{y}, Jakub and M\"{a}hlmann, Nikolas and McCarty, Rose and Ohlmann, Pierre and Pilipczuk, Micha{\l} and Przybyszewski, Wojciech and Siebertz, Sebastian and Soko{\l}owski, Marek and Toru\'{n}czyk, Szymon},
  title =	{{Flipper Games for Monadically Stable Graph Classes}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{128:1--128:16},
  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/entities/document/10.4230/LIPIcs.ICALP.2023.128},
  URN =		{urn:nbn:de:0030-drops-181804},
  doi =		{10.4230/LIPIcs.ICALP.2023.128},
  annote =	{Keywords: Stability theory, structural graph theory, games}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.58
Taming Graphs with No Large Creatures and Skinny Ladders

Authors: Jakub Gajarský, Lars Jaffke, Paloma T. Lima, Jana Novotná, Marcin Pilipczuk, Paweł Rzążewski, and Uéverton S. Souza

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class 𝒢 there exists a constant k such that no member of 𝒢 contains a k-creature as an induced subgraph or a k-skinny-ladder as an induced minor, then there exists a polynomial p such that every G ∈ 𝒢 contains at most p(|V(G)|) minimal separators. By a result of Fomin, Todinca, and Villanger [SIAM J. Comput. 2015] the latter entails the existence of polynomial-time algorithms for Maximum Weight Independent Set, Feedback Vertex Set and many other problems, when restricted to an input graph from 𝒢. Furthermore, as shown by Gartland and Lokshtanov, our result implies a full dichotomy of hereditary graph classes defined by a finite set of forbidden induced subgraphs into tame (admitting a polynomial bound of the number of minimal separators) and feral (containing infinitely many graphs with exponential number of minimal separators).
Cite as

Jakub Gajarský, Lars Jaffke, Paloma T. Lima, Jana Novotná, Marcin Pilipczuk, Paweł Rzążewski, and Uéverton S. Souza. Taming Graphs with No Large Creatures and Skinny Ladders. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 58:1-58:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gajarsky_et_al:LIPIcs.ESA.2022.58,
  author =	{Gajarsk\'{y}, Jakub and Jaffke, Lars and Lima, Paloma T. and Novotn\'{a}, Jana and Pilipczuk, Marcin and Rz\k{a}\.{z}ewski, Pawe{\l} and Souza, U\'{e}verton S.},
  title =	{{Taming Graphs with No Large Creatures and Skinny Ladders}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{58:1--58:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.58},
  URN =		{urn:nbn:de:0030-drops-169969},
  doi =		{10.4230/LIPIcs.ESA.2022.58},
  annote =	{Keywords: Minimal separator, hereditary graph class}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2022.123
Twin-Width and Types

Authors: Jakub Gajarský, Michał Pilipczuk, Wojciech Przybyszewski, and Szymon Toruńczyk

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
We study problems connected to first-order logic in graphs of bounded twin-width. Inspired by the approach of Bonnet et al. [FOCS 2020], we introduce a robust methodology of local types and describe their behavior in contraction sequences - the decomposition notion underlying twin-width. We showcase the applicability of the methodology by proving the following two algorithmic results. In both statements, we fix a first-order formula φ(x_1,…,x_k) and a constant d, and we assume that on input we are given a graph G together with a contraction sequence of width at most d. - One can in time 𝒪(n) construct a data structure that can answer the following queries in time 𝒪(log log n): given w_1,…,w_k, decide whether φ(w_1,…,w_k) holds in G. - After 𝒪(n)-time preprocessing, one can enumerate all tuples w₁,…,w_k that satisfy φ(x_1,…,x_k) in G with 𝒪(1) delay. In the first case, the query time can be reduced to 𝒪(1/ε) at the expense of increasing the construction time to 𝒪(n^{1+ε}), for any fixed ε > 0. Finally, we also apply our tools to prove the following statement, which shows optimal bounds on the VC density of set systems that are first-order definable in graphs of bounded twin-width. - Let G be a graph of twin-width d, A be a subset of vertices of G, and φ(x_1,…,x_k,y_1,…,y_l) be a first-order formula. Then the number of different subsets of A^k definable by φ using l-tuples of vertices from G as parameters, is bounded by O(|A|^l).
Cite as

Jakub Gajarský, Michał Pilipczuk, Wojciech Przybyszewski, and Szymon Toruńczyk. Twin-Width and Types. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 123:1-123:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gajarsky_et_al:LIPIcs.ICALP.2022.123,
  author =	{Gajarsk\'{y}, Jakub and Pilipczuk, Micha{\l} and Przybyszewski, Wojciech and Toru\'{n}czyk, Szymon},
  title =	{{Twin-Width and Types}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{123:1--123:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.123},
  URN =		{urn:nbn:de:0030-drops-164640},
  doi =		{10.4230/LIPIcs.ICALP.2022.123},
  annote =	{Keywords: twin-width, FO logic, model checking, query answering, enumeration}
}
Document
DOI: 10.4230/LIPIcs.CSL.2022.22
Differential Games, Locality, and Model Checking for FO Logic of Graphs

Authors: Jakub Gajarský, Maximilian Gorsky, and Stephan Kreutzer

Published in: LIPIcs, Volume 216, 30th EACSL Annual Conference on Computer Science Logic (CSL 2022)

Abstract
We introduce differential games for FO logic of graphs, a variant of Ehrenfeucht-Fraïssé games in which the game is played on only one graph and the moves of both players are restricted. We prove that these games are strong enough to capture essential information about graphs from graph classes which are interpretable in nowhere dense graph classes. This, together with the newly introduced notion of differential locality and the fact that the restriction of possible moves by the players makes it easy to decide the winner of the game in some cases, leads to a new approach to the FO model checking problem which can be used on various graph classes interpretable in classes of sparse graphs.
Cite as

Jakub Gajarský, Maximilian Gorsky, and Stephan Kreutzer. Differential Games, Locality, and Model Checking for FO Logic of Graphs. In 30th EACSL Annual Conference on Computer Science Logic (CSL 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 216, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gajarsky_et_al:LIPIcs.CSL.2022.22,
  author =	{Gajarsk\'{y}, Jakub and Gorsky, Maximilian and Kreutzer, Stephan},
  title =	{{Differential Games, Locality, and Model Checking for FO Logic of Graphs}},
  booktitle =	{30th EACSL Annual Conference on Computer Science Logic (CSL 2022)},
  pages =	{22:1--22:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-218-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{216},
  editor =	{Manea, Florin and Simpson, Alex},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2022.22},
  URN =		{urn:nbn:de:0030-drops-157426},
  doi =		{10.4230/LIPIcs.CSL.2022.22},
  annote =	{Keywords: FO model checking, locality, Gaifman’s theorem, EF games}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.56
Computing Shrub-Depth Decompositions

Authors: Jakub Gajarský and Stephan Kreutzer

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
Shrub-depth is a width measure of graphs which, roughly speaking, corresponds to the smallest depth of a tree into which a graph can be encoded. It can be thought of as a low-depth variant of clique-width (or rank-width), similarly as treedepth is a low-depth variant of treewidth. We present an fpt algorithm for computing decompositions of graphs of bounded shrub-depth. To the best of our knowledge, this is the first algorithm which computes the decomposition directly, without use of rank-width decompositions and FO or MSO logic.
Cite as

Jakub Gajarský and Stephan Kreutzer. Computing Shrub-Depth Decompositions. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 56:1-56:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gajarsky_et_al:LIPIcs.STACS.2020.56,
  author =	{Gajarsk\'{y}, Jakub and Kreutzer, Stephan},
  title =	{{Computing Shrub-Depth Decompositions}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{56:1--56:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.56},
  URN =		{urn:nbn:de:0030-drops-119177},
  doi =		{10.4230/LIPIcs.STACS.2020.56},
  annote =	{Keywords: shrub-depth, tree-model, decomposition, fixed-parameter tractability}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.29
Recovering Sparse Graphs

Authors: Jakub Gajarský and Daniel Král'

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
We construct a fixed parameter algorithm parameterized by d and k that takes as an input a graph G' obtained from a d-degenerate graph G by complementing on at most k arbitrary subsets of the vertex set of G and outputs a graph H such that G and H agree on all but f(d,k) vertices. Our work is motivated by the first order model checking in graph classes that are first order interpretable in classes of sparse graphs. We derive as a corollary that if G is a graph class with bounded expansion, then the first order model checking is fixed parameter tractable in the class of all graphs that can obtained from a graph G in G by complementing on at most k arbitrary subsets of the vertex set of G; this implies an earlier result that the first order model checking is fixed parameter tractable in graph classes interpretable in classes of graphs with bounded maximum degree.
Cite as

Jakub Gajarský and Daniel Král'. Recovering Sparse Graphs. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 29:1-29:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{gajarsky_et_al:LIPIcs.MFCS.2018.29,
  author =	{Gajarsk\'{y}, Jakub and Kr\'{a}l', Daniel},
  title =	{{Recovering Sparse Graphs}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{29:1--29:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.29},
  URN =		{urn:nbn:de:0030-drops-96111},
  doi =		{10.4230/LIPIcs.MFCS.2018.29},
  annote =	{Keywords: model checking, degenerate graphs, interpretations, bounded expansion}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.126
First-Order Interpretations of Bounded Expansion Classes

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

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

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.
Cite as

Jakub Gajarský, Stephan Kreutzer, Jaroslav Nesetril, Patrice Ossona de Mendez, Michal Pilipczuk, Sebastian Siebertz, and Szymon Torunczyk. First-Order Interpretations of Bounded Expansion Classes. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 126:1-126:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{gajarsky_et_al:LIPIcs.ICALP.2018.126,
  author =	{Gajarsk\'{y}, Jakub and Kreutzer, Stephan and Nesetril, Jaroslav and Ossona de Mendez, Patrice and Pilipczuk, Michal and Siebertz, Sebastian and Torunczyk, Szymon},
  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 =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.126},
  URN =		{urn:nbn:de:0030-drops-91300},
  doi =		{10.4230/LIPIcs.ICALP.2018.126},
  annote =	{Keywords: Logical interpretations/transductions, structurally sparse graphs, bounded expansion}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2012.112
Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences

Authors: Jakub Gajarsky and Petr Hlineny

Published in: LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

Abstract
We prove, in the universe of trees of bounded height, that for any MSO formula with $m$ variables there exists a set of kernels such that the size of each of these kernels can be bounded by an elementary function of m. This yields a faster MSO model checking algorithm for trees of bounded height than the one for general trees. From that we obtain, by means of interpretation, corresponding results for the classes of graphs of bounded tree-depth (MSO_2) and shrub-depth (MSO_1), and thus we give wide generalizations of Lampis' (ESA 2010) and Ganian's (IPEC 2011) results. In the second part of the paper we use this kernel structure to show that FO has the same expressive power as MSO_1 on the graph classes of bounded shrub-depth. This makes bounded shrub-depth a good candidate for characterization of the hereditary classes of graphs on which FO and MSO_1 coincide, a problem recently posed by Elberfeld, Grohe, and Tantau (LICS 2012).
Cite as

Jakub Gajarsky and Petr Hlineny. Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 112-123, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{gajarsky_et_al:LIPIcs.FSTTCS.2012.112,
  author =	{Gajarsky, Jakub and Hlineny, Petr},
  title =	{{Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)},
  pages =	{112--123},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.112},
  URN =		{urn:nbn:de:0030-drops-38553},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.112},
  annote =	{Keywords: MSO graph property, tree-width, tree-depth, shrub-depth}
}

Gajarský, Jakub

Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2024.137
On Classes of Bounded Tree Rank, Their Interpretations, and Efficient Sparsification

Authors: Jakub Gajarský and Rose McCarty

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
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.
Cite as

Jakub Gajarský and Rose McCarty. On Classes of Bounded Tree Rank, Their Interpretations, and Efficient Sparsification. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 137:1-137:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gajarsky_et_al:LIPIcs.ICALP.2024.137,
  author =	{Gajarsk\'{y}, Jakub and McCarty, Rose},
  title =	{{On Classes of Bounded Tree Rank, Their Interpretations, and Efficient Sparsification}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{137:1--137:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.137},
  URN =		{urn:nbn:de:0030-drops-202802},
  doi =		{10.4230/LIPIcs.ICALP.2024.137},
  annote =	{Keywords: First-order model checking, structural graph theory, structural sparsity}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.11
Sparse Graphs of Twin-Width 2 Have Bounded Tree-Width

Authors: Benjamin Bergougnoux, Jakub Gajarský, Grzegorz Guśpiel, Petr Hliněný, Filip Pokrývka, and Marek Sokołowski

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
Twin-width is a structural width parameter introduced by Bonnet, Kim, Thomassé and Watrigant [FOCS 2020]. Very briefly, its essence is a gradual reduction (a contraction sequence) of the given graph down to a single vertex while maintaining limited difference of neighbourhoods of the vertices, and it can be seen as widely generalizing several other traditional structural parameters. Having such a sequence at hand allows to solve many otherwise hard problems efficiently. Our paper focuses on a comparison of twin-width to the more traditional tree-width on sparse graphs. Namely, we prove that if a graph G of twin-width at most 2 contains no K_{t,t} subgraph for some integer t, then the tree-width of G is bounded by a polynomial function of t. As a consequence, for any sparse graph class C we obtain a polynomial time algorithm which for any input graph G ∈ C either outputs a contraction sequence of width at most c (where c depends only on C), or correctly outputs that G has twin-width more than 2. On the other hand, we present an easy example of a graph class of twin-width 3 with unbounded tree-width, showing that our result cannot be extended to higher values of twin-width.
Cite as

Benjamin Bergougnoux, Jakub Gajarský, Grzegorz Guśpiel, Petr Hliněný, Filip Pokrývka, and Marek Sokołowski. Sparse Graphs of Twin-Width 2 Have Bounded Tree-Width. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 11:1-11:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bergougnoux_et_al:LIPIcs.ISAAC.2023.11,
  author =	{Bergougnoux, Benjamin and Gajarsk\'{y}, Jakub and Gu\'{s}piel, Grzegorz and Hlin\v{e}n\'{y}, Petr and Pokr\'{y}vka, Filip and Soko{\l}owski, Marek},
  title =	{{Sparse Graphs of Twin-Width 2 Have Bounded Tree-Width}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{11:1--11:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.11},
  URN =		{urn:nbn:de:0030-drops-193130},
  doi =		{10.4230/LIPIcs.ISAAC.2023.11},
  annote =	{Keywords: twin-width, tree-width, excluded grid, sparsity}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2023.128
Flipper Games for Monadically Stable Graph Classes

Authors: Jakub Gajarský, Nikolas Mählmann, Rose McCarty, Pierre Ohlmann, Michał Pilipczuk, Wojciech Przybyszewski, Sebastian Siebertz, Marek Sokołowski, and Szymon Toruńczyk

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
A class of graphs C is monadically stable if for every unary expansion Ĉ of C, one cannot encode - using first-order transductions - arbitrarily long linear orders in graphs from C. It is known that nowhere dense graph classes are monadically stable; these include classes of bounded maximum degree and classes that exclude a fixed topological minor. On the other hand, monadic stability is a property expressed in purely model-theoretic terms that is also suited for capturing structure in dense graphs. In this work we provide a characterization of monadic stability in terms of the Flipper game: a game on a graph played by Flipper, who in each round can complement the edge relation between any pair of vertex subsets, and Localizer, who in each round is forced to restrict the game to a ball of bounded radius. This is an analog of the Splitter game, which characterizes nowhere dense classes of graphs (Grohe, Kreutzer, and Siebertz, J. ACM '17). We give two different proofs of our main result. The first proof is based on tools borrowed from model theory, and it exposes an additional property of monadically stable graph classes that is close in spirit to definability of types. Also, as a byproduct, we show that monadic stability for graph classes coincides with monadic stability of existential formulas with two free variables, and we provide another combinatorial characterization of monadic stability via forbidden patterns. The second proof relies on the recently introduced notion of flip-flatness (Dreier, Mählmann, Siebertz, and Toruńczyk, arXiv 2206.13765) and provides an efficient algorithm to compute Flipper’s moves in a winning strategy.
Cite as

Jakub Gajarský, Nikolas Mählmann, Rose McCarty, Pierre Ohlmann, Michał Pilipczuk, Wojciech Przybyszewski, Sebastian Siebertz, Marek Sokołowski, and Szymon Toruńczyk. Flipper Games for Monadically Stable Graph Classes. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 128:1-128:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gajarsky_et_al:LIPIcs.ICALP.2023.128,
  author =	{Gajarsk\'{y}, Jakub and M\"{a}hlmann, Nikolas and McCarty, Rose and Ohlmann, Pierre and Pilipczuk, Micha{\l} and Przybyszewski, Wojciech and Siebertz, Sebastian and Soko{\l}owski, Marek and Toru\'{n}czyk, Szymon},
  title =	{{Flipper Games for Monadically Stable Graph Classes}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{128:1--128:16},
  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/entities/document/10.4230/LIPIcs.ICALP.2023.128},
  URN =		{urn:nbn:de:0030-drops-181804},
  doi =		{10.4230/LIPIcs.ICALP.2023.128},
  annote =	{Keywords: Stability theory, structural graph theory, games}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.58
Taming Graphs with No Large Creatures and Skinny Ladders

Authors: Jakub Gajarský, Lars Jaffke, Paloma T. Lima, Jana Novotná, Marcin Pilipczuk, Paweł Rzążewski, and Uéverton S. Souza

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class 𝒢 there exists a constant k such that no member of 𝒢 contains a k-creature as an induced subgraph or a k-skinny-ladder as an induced minor, then there exists a polynomial p such that every G ∈ 𝒢 contains at most p(|V(G)|) minimal separators. By a result of Fomin, Todinca, and Villanger [SIAM J. Comput. 2015] the latter entails the existence of polynomial-time algorithms for Maximum Weight Independent Set, Feedback Vertex Set and many other problems, when restricted to an input graph from 𝒢. Furthermore, as shown by Gartland and Lokshtanov, our result implies a full dichotomy of hereditary graph classes defined by a finite set of forbidden induced subgraphs into tame (admitting a polynomial bound of the number of minimal separators) and feral (containing infinitely many graphs with exponential number of minimal separators).
Cite as

Jakub Gajarský, Lars Jaffke, Paloma T. Lima, Jana Novotná, Marcin Pilipczuk, Paweł Rzążewski, and Uéverton S. Souza. Taming Graphs with No Large Creatures and Skinny Ladders. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 58:1-58:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gajarsky_et_al:LIPIcs.ESA.2022.58,
  author =	{Gajarsk\'{y}, Jakub and Jaffke, Lars and Lima, Paloma T. and Novotn\'{a}, Jana and Pilipczuk, Marcin and Rz\k{a}\.{z}ewski, Pawe{\l} and Souza, U\'{e}verton S.},
  title =	{{Taming Graphs with No Large Creatures and Skinny Ladders}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{58:1--58:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.58},
  URN =		{urn:nbn:de:0030-drops-169969},
  doi =		{10.4230/LIPIcs.ESA.2022.58},
  annote =	{Keywords: Minimal separator, hereditary graph class}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2022.123
Twin-Width and Types

Authors: Jakub Gajarský, Michał Pilipczuk, Wojciech Przybyszewski, and Szymon Toruńczyk

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
We study problems connected to first-order logic in graphs of bounded twin-width. Inspired by the approach of Bonnet et al. [FOCS 2020], we introduce a robust methodology of local types and describe their behavior in contraction sequences - the decomposition notion underlying twin-width. We showcase the applicability of the methodology by proving the following two algorithmic results. In both statements, we fix a first-order formula φ(x_1,…,x_k) and a constant d, and we assume that on input we are given a graph G together with a contraction sequence of width at most d. - One can in time 𝒪(n) construct a data structure that can answer the following queries in time 𝒪(log log n): given w_1,…,w_k, decide whether φ(w_1,…,w_k) holds in G. - After 𝒪(n)-time preprocessing, one can enumerate all tuples w₁,…,w_k that satisfy φ(x_1,…,x_k) in G with 𝒪(1) delay. In the first case, the query time can be reduced to 𝒪(1/ε) at the expense of increasing the construction time to 𝒪(n^{1+ε}), for any fixed ε > 0. Finally, we also apply our tools to prove the following statement, which shows optimal bounds on the VC density of set systems that are first-order definable in graphs of bounded twin-width. - Let G be a graph of twin-width d, A be a subset of vertices of G, and φ(x_1,…,x_k,y_1,…,y_l) be a first-order formula. Then the number of different subsets of A^k definable by φ using l-tuples of vertices from G as parameters, is bounded by O(|A|^l).
Cite as

Jakub Gajarský, Michał Pilipczuk, Wojciech Przybyszewski, and Szymon Toruńczyk. Twin-Width and Types. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 123:1-123:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gajarsky_et_al:LIPIcs.ICALP.2022.123,
  author =	{Gajarsk\'{y}, Jakub and Pilipczuk, Micha{\l} and Przybyszewski, Wojciech and Toru\'{n}czyk, Szymon},
  title =	{{Twin-Width and Types}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{123:1--123:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.123},
  URN =		{urn:nbn:de:0030-drops-164640},
  doi =		{10.4230/LIPIcs.ICALP.2022.123},
  annote =	{Keywords: twin-width, FO logic, model checking, query answering, enumeration}
}
Document
DOI: 10.4230/LIPIcs.CSL.2022.22
Differential Games, Locality, and Model Checking for FO Logic of Graphs

Authors: Jakub Gajarský, Maximilian Gorsky, and Stephan Kreutzer

Published in: LIPIcs, Volume 216, 30th EACSL Annual Conference on Computer Science Logic (CSL 2022)

Abstract
We introduce differential games for FO logic of graphs, a variant of Ehrenfeucht-Fraïssé games in which the game is played on only one graph and the moves of both players are restricted. We prove that these games are strong enough to capture essential information about graphs from graph classes which are interpretable in nowhere dense graph classes. This, together with the newly introduced notion of differential locality and the fact that the restriction of possible moves by the players makes it easy to decide the winner of the game in some cases, leads to a new approach to the FO model checking problem which can be used on various graph classes interpretable in classes of sparse graphs.
Cite as

Jakub Gajarský, Maximilian Gorsky, and Stephan Kreutzer. Differential Games, Locality, and Model Checking for FO Logic of Graphs. In 30th EACSL Annual Conference on Computer Science Logic (CSL 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 216, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gajarsky_et_al:LIPIcs.CSL.2022.22,
  author =	{Gajarsk\'{y}, Jakub and Gorsky, Maximilian and Kreutzer, Stephan},
  title =	{{Differential Games, Locality, and Model Checking for FO Logic of Graphs}},
  booktitle =	{30th EACSL Annual Conference on Computer Science Logic (CSL 2022)},
  pages =	{22:1--22:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-218-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{216},
  editor =	{Manea, Florin and Simpson, Alex},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2022.22},
  URN =		{urn:nbn:de:0030-drops-157426},
  doi =		{10.4230/LIPIcs.CSL.2022.22},
  annote =	{Keywords: FO model checking, locality, Gaifman’s theorem, EF games}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.56
Computing Shrub-Depth Decompositions

Authors: Jakub Gajarský and Stephan Kreutzer

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
Shrub-depth is a width measure of graphs which, roughly speaking, corresponds to the smallest depth of a tree into which a graph can be encoded. It can be thought of as a low-depth variant of clique-width (or rank-width), similarly as treedepth is a low-depth variant of treewidth. We present an fpt algorithm for computing decompositions of graphs of bounded shrub-depth. To the best of our knowledge, this is the first algorithm which computes the decomposition directly, without use of rank-width decompositions and FO or MSO logic.
Cite as

Jakub Gajarský and Stephan Kreutzer. Computing Shrub-Depth Decompositions. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 56:1-56:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gajarsky_et_al:LIPIcs.STACS.2020.56,
  author =	{Gajarsk\'{y}, Jakub and Kreutzer, Stephan},
  title =	{{Computing Shrub-Depth Decompositions}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{56:1--56:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.56},
  URN =		{urn:nbn:de:0030-drops-119177},
  doi =		{10.4230/LIPIcs.STACS.2020.56},
  annote =	{Keywords: shrub-depth, tree-model, decomposition, fixed-parameter tractability}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.29
Recovering Sparse Graphs

Authors: Jakub Gajarský and Daniel Král'

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
We construct a fixed parameter algorithm parameterized by d and k that takes as an input a graph G' obtained from a d-degenerate graph G by complementing on at most k arbitrary subsets of the vertex set of G and outputs a graph H such that G and H agree on all but f(d,k) vertices. Our work is motivated by the first order model checking in graph classes that are first order interpretable in classes of sparse graphs. We derive as a corollary that if G is a graph class with bounded expansion, then the first order model checking is fixed parameter tractable in the class of all graphs that can obtained from a graph G in G by complementing on at most k arbitrary subsets of the vertex set of G; this implies an earlier result that the first order model checking is fixed parameter tractable in graph classes interpretable in classes of graphs with bounded maximum degree.
Cite as

Jakub Gajarský and Daniel Král'. Recovering Sparse Graphs. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 29:1-29:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{gajarsky_et_al:LIPIcs.MFCS.2018.29,
  author =	{Gajarsk\'{y}, Jakub and Kr\'{a}l', Daniel},
  title =	{{Recovering Sparse Graphs}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{29:1--29:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.29},
  URN =		{urn:nbn:de:0030-drops-96111},
  doi =		{10.4230/LIPIcs.MFCS.2018.29},
  annote =	{Keywords: model checking, degenerate graphs, interpretations, bounded expansion}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.126
First-Order Interpretations of Bounded Expansion Classes

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

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

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.
Cite as

Jakub Gajarský, Stephan Kreutzer, Jaroslav Nesetril, Patrice Ossona de Mendez, Michal Pilipczuk, Sebastian Siebertz, and Szymon Torunczyk. First-Order Interpretations of Bounded Expansion Classes. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 126:1-126:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{gajarsky_et_al:LIPIcs.ICALP.2018.126,
  author =	{Gajarsk\'{y}, Jakub and Kreutzer, Stephan and Nesetril, Jaroslav and Ossona de Mendez, Patrice and Pilipczuk, Michal and Siebertz, Sebastian and Torunczyk, Szymon},
  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 =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.126},
  URN =		{urn:nbn:de:0030-drops-91300},
  doi =		{10.4230/LIPIcs.ICALP.2018.126},
  annote =	{Keywords: Logical interpretations/transductions, structurally sparse graphs, bounded expansion}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2012.112
Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences

Authors: Jakub Gajarsky and Petr Hlineny

Published in: LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

Abstract
We prove, in the universe of trees of bounded height, that for any MSO formula with $m$ variables there exists a set of kernels such that the size of each of these kernels can be bounded by an elementary function of m. This yields a faster MSO model checking algorithm for trees of bounded height than the one for general trees. From that we obtain, by means of interpretation, corresponding results for the classes of graphs of bounded tree-depth (MSO_2) and shrub-depth (MSO_1), and thus we give wide generalizations of Lampis' (ESA 2010) and Ganian's (IPEC 2011) results. In the second part of the paper we use this kernel structure to show that FO has the same expressive power as MSO_1 on the graph classes of bounded shrub-depth. This makes bounded shrub-depth a good candidate for characterization of the hereditary classes of graphs on which FO and MSO_1 coincide, a problem recently posed by Elberfeld, Grohe, and Tantau (LICS 2012).
Cite as

Jakub Gajarsky and Petr Hlineny. Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 112-123, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{gajarsky_et_al:LIPIcs.FSTTCS.2012.112,
  author =	{Gajarsky, Jakub and Hlineny, Petr},
  title =	{{Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)},
  pages =	{112--123},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.112},
  URN =		{urn:nbn:de:0030-drops-38553},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.112},
  annote =	{Keywords: MSO graph property, tree-width, tree-depth, shrub-depth}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact