2026-07-21T15:08:03Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:26184 2026-07-02T07:14:09Z ddc:004 open_access
Polynomial Kernels for Spanning Tree with Diversity Requirements Golovach, Petr A. Majumdar, Diptapriyo Saurabh, Saket Parameterized Complexity Kernelization Diverse Solutions Diverse Spanning Trees 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 𝓁 spanning trees T₁,…,T_{𝓁} is {{pairwise k-diverse}} if for every i β‰  j, |E(T_i) β–³ E(T_j)| β‰₯ k. Given a connected undirected graph G and integers p, q, k, 𝓁, {Leaf&Internal-Constrained Diverse Spanning Trees} asks whether there are 𝓁 distinct spanning trees T₁,…,T_{𝓁} 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 βŠ† V(G), and three integers p, k, 𝓁, and asks if G has 𝓁 spanning trees that are {{pairwise k-diverse}}, and each has at least p leaves and contains 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 + 𝓁 and p + |V_NT| + k + 𝓁, respectively. Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik Petr A. Golovach and Diptapriyo Majumdar and Saket Saurabh 2026 Is Part Of LIPIcs, Volume 376, 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WG.2026.18 urn:nbn:de:0030-drops-261840 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WG.2026.18 eng https://creativecommons.org/licenses/by/4.0/legalcode