Finding k-secluded trees faster

作     者：Donkers, Huib Jansen, Bart M. P. de Kroon, Jari J. H. 

作者机构：Eindhoven Univ Technol Eindhoven Netherlands 

出 版 物：《JOURNAL OF COMPUTER AND SYSTEM SCIENCES》 (计算机与系统科学杂志)

年 卷 期：2023年第138卷第1期

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：NWO Gravitation grant "Networks" [024.002.003] ERC European Research Council (ERC) Funding Source: European Research Council (ERC) 

主　　题：Secluded tree FPT Enumeration algorithm 

摘      要：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 2O(k log k) nO(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 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 them as well.2023 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).