{"ID":2885217,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.05351","arxiv_id":"2508.05351","title":"Parameterized Algorithms for Spanning Tree Isomorphism by Redundant Set Size","abstract":"In this paper, we present fixed-parameter tractability algorithms for both the undirected and directed versions of the Spanning Tree Isomorphism Problem, parameterized by the size $k$ of a redundant set. A redundant set is a collection of edges whose removal transforms the graph into a spanning tree. For the undirected version, our algorithm achieves a time complexity of $O(n^2 \\log n \\cdot 2^{k \\log k})$. For the directed version, we propose a more efficient algorithm with a time complexity of $O(n^2 \\cdot 2^{4k-3})$, where $n$ is the number of vertices.","short_abstract":"In this paper, we present fixed-parameter tractability algorithms for both the undirected and directed versions of the Spanning Tree Isomorphism Problem, parameterized by the size $k$ of a redundant set. A redundant set is a collection of edges whose removal transforms the graph into a spanning tree. For the undirected...","url_abs":"https://arxiv.org/abs/2508.05351","url_pdf":"https://arxiv.org/pdf/2508.05351v1","authors":"[\"Fangjian Shen\",\"Yicheng Zheng\",\"Wushao Wen\",\"Hankz Hankui Zhuo\"]","published":"2025-08-07T12:58:30Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}