Search Results

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^↓, 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 Independent Set, Maximum Clique, Maximum Induced d-Regular Subgraph, and Induced Disjoint Paths in graphs given with a contraction sequence witnessing low cml^↓, 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^↓: bounded maximum degree implies bounded treewidth, whereas K_{t,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^↓ admit balanced separators dominated by a bounded number of vertices. In contrast, there are graphs G of arbitrarily large girth and treewidth Θ(|V(G)|^{1/2}) such that cml^↓(G) ⩽ 3. We then showcase an application of the reduced parameters to establishing non-transducibility results. We prove that for most reduced parameters p^↓ (including reduced bandwidth), the family of classes of bounded p^↓ 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; HJ, LICS '25] that planar graphs do not first-order transduce the 3-dimensional grids.