cs.DS

# Title: Finding $k$-Secluded Trees Faster

Abstract: We revisit the \textsc{$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^{\mathcal{O}(k \log k)}\cdot n^{\mathcal{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.
 Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC) Cite as: arXiv:2206.09884 [cs.DS] (or arXiv:2206.09884v1 [cs.DS] for this version)

## Submission history

From: Huib Donkers [view email]
[v1] Mon, 20 Jun 2022 16:39:39 GMT (53kb)
[v2] Fri, 24 Jun 2022 16:05:50 GMT (53kb)

Link back to: arXiv, form interface, contact.
{"ft_lang_label":"__label__en","ft_lang_prob":0.82641757,"math_prob":0.9601483,"size":1494,"snap":"2022-40-2023-06","text_gpt3_token_len":386,"char_repetition_ratio":0.102013424,"word_repetition_ratio":0.0,"special_character_ratio":0.25301206,"punctuation_ratio":0.11231884,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9635904,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-10-05T10:09:27Z\",\"WARC-Record-ID\":\"<urn:uuid:c3314b11-3557-4a4d-9540-9059ca22f590>\",\"Content-Length\":\"16605\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:3138a3d9-f04c-46d7-9dfa-93fb66664da3>\",\"WARC-Concurrent-To\":\"<urn:uuid:43c9fa56-c1a1-49c9-a054-6ce1a80195e5>\",\"WARC-IP-Address\":\"128.84.21.203\",\"WARC-Target-URI\":\"http://export.arxiv.org/abs/2206.09884v1\",\"WARC-Payload-Digest\":\"sha1:J43HHKL6INF5CROFYAKS23AYQR4CFQ2H\",\"WARC-Block-Digest\":\"sha1:2MLN6URBG7RIOIS5WJG7PZUKVGAS45UM\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-40/CC-MAIN-2022-40_segments_1664030337595.1_warc_CC-MAIN-20221005073953-20221005103953-00681.warc.gz\"}"}