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 problem in directed graphs by incorporating different notions of neighborhoods: in-neighborhood, out-neighborhood, and their union. Formally, we call these problems $\{\text{In}, \text{Out}, \text{Total}\}$-Secluded $Π$-Subgraph, where given a directed graph $G$ and integers $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 In/Out-Secluded $\mathcal{F}$-Free Subgraph problem with parameter $k+w$ is W[1]-hard, where $\mathcal{F}$ 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^kn^{\mathcal{O}(1)}$.

翻译：给定一个无向图$G$和一个整数$k$，孤立$Π$-子图问题要求找到一个满足性质$Π$且在图其余部分中至多有$k$个邻居的最大规模诱导子图。该问题已被广泛研究；然而，目前尚无关于该问题在有向图中研究的先例。Jansen等人[ISAAC'23]曾提及此问题。本文通过引入不同的邻域概念：入邻域、出邻域及其并集，首次在有向图中开展孤立子图问题的研究。形式上，我们称这些问题为$\{\text{In}, \text{Out}, \text{Total}\}$-孤立$Π$-子图问题，其中给定一个有向图$G$和整数$k$，我们需分别找到一个满足性质$Π$且在图其余部分中至多有$k$个入/出/总邻居的最大规模诱导子图。我们针对不同性质$Π$研究了这些问题的参数化复杂度。特别地，我们证明了以下参数化结果：- 当以$k$为参数时，我们为Total-孤立强连通子图问题设计了FPT算法。- 我们证明以$k+w$为参数的In/Out-孤立$\mathcal{F}$-自由子图问题是W[1]-难的，其中$\mathcal{F}$是除任何边指向中心的星图子图外的有向图族。该结果也意味着In/Out-孤立DAG是W[1]-难的，这与两个问题的无向变体（均为FPT）不同。- 当以$k$为参数时，我们为In/Out/Total-孤立$α$-有界子图设计了FPT算法，其中$α$-有界图是竞赛图的超类。- 对于无向图，我们通过提供运行时间为$1.6181^kn^{\mathcal{O}(1)}$的更快速FPT算法，改进了孤立团问题的最佳已知FPT算法。