Papers › Transducing paths in graph classes with unbounded shrubdepth
Transducing paths in graph classes with unbounded shrubdepth
Michał Pilipczuk, Patrice Ossona de Mendez, Sebastian Siebertz
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
Transductions are a general formalism for expressing transformations of graphs (and more generally, of relational structures) in logic. We prove that a graph class 𝒞 can be 𝖥𝖮-transduced from a class of bounded-height trees (that is, has bounded shrubdepth) if, and only if, from 𝒞 one cannot 𝖥𝖮-transduce the class of all paths. This establishes one of the three remaining open questions posed by Blumensath and Courcelle about the 𝖬𝖲𝖮-transduction quasi-order, even in the stronger form that concerns 𝖥𝖮-transductions instead of 𝖬𝖲𝖮-transductions. The backbone of our proof is a graph-theoretic statement that says the following: If a graph G excludes a path, the bipartite complement of a path, and a half-graph as semi-induced subgraphs, then the vertex set of G can be partitioned into a bounded number of parts so that every part induces a cograph of bounded height, and every pair of parts semi-induce a bi-cograph of bounded height. This statement may be of independent interest; for instance, it implies that the graphs in question form a class that is linearly χ-bounded.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections