Polynomial Kernels for Spanning Tree with Diversity Requirements

Abstract

Given a connected undirected graph $G$, a spanning tree is a subgraph $T$ of $G$ such that $V(T)=V(G)$ and $T$ is a tree. A collection of $\ell$ spanning trees $T_1,\dots ,T_{\ell }$ is pairwise $k$-diverse if for every $i\ne j$, $|E(T_i)△E(T_j)|\ge k$. Given a connected undirected graph $G$ and integers $p,q,k,\ell$, Leaf & Internal-Constrained Diverse Spanning Trees asks whether there are $\ell$ distinct spanning trees $T_1,\dots ,T_{\ell }$ of $G$ that are pairwise $k$-diverse such that each tree has at least $p$ leaves and at least $q$ internal vertices. Similarly, Leaf & Non-terminal-Constrained Diverse Spanning Trees takes a connected undirected graph $G$, $V_{NT}\subseteq V(G)$, and three integers $p,k,\ell$, and asks if $G$ has $\ell$ spanning trees that are pairwise $k$-diverse, and each has at least $p$ leaves and conains the vertices of $V_{NT}$ as internal. We consider these two problems from the kernelization perspective and provide polynomial kernels for Leaf & Internal-Constrained Diverse Spanning Trees and Leaf & Non-terminal-Constrained Diverse Spanning Trees, when parameterized by $p+q+k+\ell$ and $p+|V_{\mathrm{NT}}|+k+\ell$, respectively.

Accepted for WG 2026