2026/04/21 by Édouard Bonnet, Yeonsu Chang, Julien Duron +2 · 1 voice
Computer Science · Mathematics · #Advanced Graph Theory Research #Bounded function #Class (philosophy) #Complexity and Algorithms in Graphs #Component (thermodynamics) #Disjoint sets #Distributed systems and fault tolerance #Interval (graph theory) #Planar #Planar graph #Sublinear function #cs.DM #cs.DS #math.CO
paper · pdf · doi:10.48550/arxiv.2604.19138
openalex publication_date 2026/04/21 · arxiv published 2026/04/21 · arxiv updated 2026/04/21 · openalex created_date 2026/04/23 · openalex updated_date 2026/07/28
Reduced parameters [BKW, JCTB '26; BKRT, SODA '22] are defined via contraction sequences. Based on this framework, we introduce the reduced component max-leaf, denoted by cml^\downarrow, where component max-leaf is the maximum number of leaves in any spanning tree of any connected component. Reduced component max-leaf is strictly sandwiched between clique-width and reduced bandwidth, it is bounded in unit interval graphs, and unbounded in planar graphs. We design polynomial-time algorithms for problems such as Maximum Induced d-Regular Subgraph and Induced Disjoint Paths in graphs given with a contraction sequence witnessing low cml^\downarrow, unifying and extending tractability results for classes of bounded clique-width and unit interval graphs. We get the following collapses in sparse classes of bounded cml^\downarrow: bounded maximum degree implies bounded treewidth, whereas Kt,t-subgraph-freeness implies strongly sublinear treewidth; we show the latter, more generally, for classes of bounded reduced cutwidth. We establish the former result by showing that graphs with bounded cml^\downarrow admit balanced separators dominated by a bounded number of vertices. We then showcase an application of the reduced parameters to establishing non-transducibility results. We prove that for most reduced parameters p^\downarrow (including reduced bandwidth), the family of classes of bounded p^\downarrow is closed under first-order transductions. We then answer a question of [BKW '26] by showing that the 3-dimensional grids have unbounded reduced bandwidth. As the class of planar graphs (or any class of bounded genus) has bounded reduced bandwidth [BKW '26], this reproves a recent result [GPP, LICS '25] that planar graphs do not first-order transduce the 3-dimensional grids.