Finding k-Secluded Trees Faster
We revisit the \(k\)-Secluded Tree problem. Given a vertex-weighted undirected graph \(G\), its objective is to find a maximum-weight induced subtree\(T\) whose open neighborhood has size at most \(k\). We present a fixed-parameter tractable algorithm that solves the problem in time \(2^{O(k \log k)}* n^{O(1)}\), improving on a double-exponential running time from earlier work by Golovach, Heggernes, Lima, and Montealegre. Starting from a single vertex, our algorithm grows a \(k\)-secluded tree by branching on vertices in the open neighborhood of the current tree\(T\). To bound the branching depth, we prove a structural result that can be used to identify a vertex that belongs to the neighborhood of any \(k\)-secluded supertree \(T’ \supseteq T\) once the open neighborhood of \(T\) becomes sufficiently large. We extend the algorithm to enumerate compact descriptions of all maximum-weight \(k\)-secluded trees, which allows us to count the number of maximum-weight \(k\)-secluded trees containing a specified vertex in the same running time.