{"id":"arxiv/2604.19138","url":"https://arxiv.org/abs/2604.19138","tags":["cs.DS","cs.DM","math.CO"],"score":0,"title":"Moderately beyond clique-width: reduced component max-leaf and related parameters","domain":"cs.DS","source":"arxiv","authors":["Édouard Bonnet","Yeonsu Chang","Julien Duron","Colin Geniet","O-joung Kwon"],"reviews":0,"subject":"cs.DS","summary":"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 $\\operatorname{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 \\textsc{Maximum Induced $d$-Regular Subgraph} and \\textsc{Induced…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-04-21","reactions":{}}