2026-07-23T02:49:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24961 2026-02-09T08:02:39Z ddc:004 open_access

A Parameterized Study of Secluded Structures in Directed Graphs Schmidt, Jonas Verma, Shaily Mallek, Nadym Secluded Subgraph Parametrized Complexity Directed Graphs Strong Connectivity Given an undirected graph G and an integer k, the Secluded Π-Subgraph problem asks you to find a maximum size induced subgraph that satisfies a property Π and has at most k neighbors in the rest of the graph. This problem has been extensively studied; however, there is no prior study of the problem in directed graphs. This question has been mentioned by Jansen et al. [ISAAC'23]. In this paper, we initiate the study of Secluded Subgraph problems in directed graphs by incorporating different notions of neighborhoods: in-neighborhood, out-neighborhood, and their union. Formally, we call these problems {In, Out, Total}-Secluded Π-Subgraph, where given a directed graph G and an integer k, we want to find an induced subgraph satisfying Π of maximum size that has at most k in/out/total-neighbors in the rest of the graph, respectively. We investigate the parameterized complexity of these problems for different properties Π. In particular, we prove the following parameterized results: - We design an FPT algorithm for the Total-Secluded Strongly Connected Subgraph problem when parameterized by k. - We show that the Out-Secluded ℱ-Free Subgraph problem with parameter k is W[1]-hard, where ℱ is a family of directed graphs except any subgraph of a star graph whose edges are directed towards the center. This result also implies that In/Out-Secluded DAG is W[1]-hard, unlike the undirected variants of the two problems, which are FPT. - We design an FPT-algorithm for In/Out/Total-Secluded α-Bounded Subgraph when parameterized by k, where α-bounded graphs are a superclass of tournaments. - For undirected graphs, we improve the best-known FPT algorithm for Secluded Clique by providing a faster FPT algorithm that runs in time 1.6181^k n^𝒪(1). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jonas Schmidt and Shaily Verma and Nadym Mallek 2025 Is Part Of LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2025.53 urn:nbn:de:0030-drops-249616 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.53 eng https://creativecommons.org/licenses/by/4.0/legalcode