Polynomial Kernels for Spanning Tree with Diversity Requirements
For parameterized complexity researchers, this gives polynomial-time preprocessing for constrained spanning tree diversity problems.
The paper provides polynomial kernels for two variants of the Diverse Spanning Trees problem with leaf and internal vertex constraints, parameterized by the sum of the constraints and diversity parameters.
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,\ldots,T_\ell$ is pairwise $k$-diverse if for every $i \neq j$, $|E(T_i) \triangle E(T_j)| \geq 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,\ldots,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_{\rm NT}| + k + \ell$, respectively.