Finding k-secluded trees faster

Huib Donkers, Bart M.P. Jansen, Jari J.H. de Kroon (Corresponding author)

Research output: Contribution to journalArticleAcademicpeer-review

26 Downloads (Pure)

Abstract

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(klog⁡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 ⊇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.

Original languageEnglish
Article number103461
Number of pages17
JournalJournal of Computer and System Sciences
Volume138
DOIs
Publication statusPublished - Dec 2023

Funding

Supported by NWO Gravitation grant “Networks” (No. 024.002.003).Supported by ERC Starting grant 803421, “ReduceSearch”.

FundersFunder number
European Research Council803421
Nederlandse Organisatie voor Wetenschappelijk Onderzoek024.002.003

    Keywords

    • Enumeration algorithm
    • FPT
    • Secluded tree

    Fingerprint

    Dive into the research topics of 'Finding k-secluded trees faster'. Together they form a unique fingerprint.

    Cite this