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.

17 pages, no figures, submitted to SODA2026