A Parameterized Study of Secluded Structures in Directed Graphs

Nadym Mallek, Jonas Schmidt, Shaily Verma · 2025

Read A Parameterized Study of Secluded Structures in Directed Graphs by Nadym Mallek, Jonas Schmidt, Shaily Verma (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-06048.txt.

Introduction

Jonas Schmidt, Shaily Verma, and Nadym Mallek open a new front in the hunt for secluded graph structures. Their paper appeared in two thousand twenty-five. A secluded subgraph is large, well-behaved, and barely connected to the rest. The undirected version has been studied for years. Directed graphs, where edges have arrows, were untouched. Jansen and others had flagged the gap.

Three neighborhood notions arise from the arrows. In-neighbors, out-neighbors, and their union each define a variant. The authors map the parameterized complexity of each. Tractability depends on the property sought and the neighbor budget. Algorithms and hardness results fill the map. Directed network analysis gains a formal notion of quiet corners.

Catalog record

CREATORNadym Mallek, Jonas Schmidt, Shaily Verma
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE94 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-06048

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Parameterized Study of Secluded Structures in Directed Graphs Nadym Mallek, Jonas Schmidt, Shaily Verma Abstract Given an undirected graph G G and an integer k k , the Secluded Π \Pi -Subgraph problem asks you to find a maximum size induced subgraph that satisfies a property Π \Pi and has at most k 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 { In, Out, Total } -Secluded Π \Pi -Subgraph , where given a directed graph G G and integers k k , we want to find an induced subgraph satisfying Π \Pi of maximum size that has at most k k in/out/total-neighbors in the rest of the graph, respectively. We investigate the parameterized complexity of these problems for different properties Π \Pi . 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 k . • We show that the In/Out-Secluded ℱ \mathcal{F} -Free Subgraph problem with parameter k + w 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 α \alpha -Bounded Subgraph when parameterized by k k , where α \alpha -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 ) 1.6181^{k}n^{\mathcal{O}(1)} . \Crefname reduction*Reduction RuleReduction Rules \Crefname stepStepSteps \Crefname enumiStepSteps \crefname theoremThm.Thms. \Crefname theoremTheoremTheorems \crefname corollaryCor.Cors. \Crefname corollaryCorollaryCorollaries Hasso Plattner Institute, Potsdam, [email protected] Bocconi University, Milan, [email protected]://orcid.org/0000-0002-1115-3868 Hasso Plattner Institute, Potsdam, [email protected] {CCSXML} ¡ccs2012¿ ¡concept¿ ¡concept_id¿10003752.10003809.10003716¡/concept_id¿ ¡concept_desc¿Theory of computation Graph algorithms analysis¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡concept¿ ¡concept_id¿10003752.10003809.10010170¡/concept_id¿ ¡concept_desc¿Theory of computation Parameterized complexity¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡/ccs2012¿ ccs Theory of computation Graph algorithms analysis ccs Theory of computation Parameterized complexity keywords Secluded Subgraph, Parametrized Complexity, Directed Graphs, Strong Connectivity † † runningtitle: A Parameterized Study of Secluded Structures in Directed Graphs † † runningauthor: N. Mallek, J. Schmidt, and S. Verma † † copyright: Nadym Mallek, Jonas Schmidt, and Shaily Verma 1 Introduction Finding substructures in graphs that satisfy specific properties is a ubiquitous problem. This general class of problems covers many classical graph problems such as finding maximum cliques, Steiner trees, or even shortest paths. Another compelling property to look for in a substructure is its isolation from the remaining graph. This motivated Chechik et al. [ 1 ] , to introduce the concept of secluded subgraphs . Formally, in the Secluded \propOp -Subgraph problem, given an undirected graph G , the goal is to find a maximum size subset of vertices S\subseteq\vOp({G}) such that the subgraph induced on S fulfills a property \propOp and has a neighborhood \left|\neiOp({S})\right|\leq k where k is a natural number. This problem has been studied extensively for various properties \propOp such as paths [ 22 , 17 , 8 , 1 ] , Steiner trees [ 1 , 8 ] , induced trees [ 7 , 11 ] , subgraphs free of forbidden induced subgraphs [ 11 , 15 ] , and more [ 21 ] . Most of these studies focus on the parameterized setting, due to the strong relation to vertex deletion and separator problems, which are foundational in parameterized complexity. Our problem fits in that category since the neighborhood can be considered a (S,V\setminus S) -separator. While the undirected Secluded \Pi -Subgraph problem has been explored and widely understood in prior work [ 15 , 11 , 7 ] , the directed variant has not yet been studied, although it is a natural generalization and was mentioned as an interesting direction by Jansen et al. [ 15 ] . Directed graphs naturally model real-world systems with asymmetric interactions, such as social networks with unidirectional follow mechanisms or information flow in communication systems. Furthermore, problems such as Directed Feedback Vertex Set , Directed Multicut , and Directed Multiway Cut underline how directedness can make a fascinating and insightful difference when it comes to parametrized complexity [ 2 , 13 , 19 , 4 ] . These problems and their results provide a ground for studying directed secluded subgraph problems, motivating the need to investigate them systematically. In this paper, we introduce and study three natural directed variants of the Secluded \Pi -Subgraph problem, namely Out-Secluded \Pi -Subgraph , In-Secluded \Pi -Subgraph , and Total-Secluded \Pi -Subgraph . These problems aim to minimize either the out-neighborhood of S , its in-neighborhood, or the union of both. The out/in-neighborhood of a set S is the set of vertices reachable from S via an outgoing/incoming edge. These problems corresponding to different types of neighborhoods can be encountered in real-life networks. For example, in privacy-aware social network analysis, one might aim to identify a community with minimal external exposure. Similarly, robust substructures with limited connectivity to vulnerable components are critical in cybersecurity. These real-world motivations further emphasize the need to explore and formalize directed variants of the Secluded \Pi -Subgraph problem. Problem In- / Out-Secluded Total-Secluded WC \mathcal{F} -Free Subgraph W[1]-hard \cref thm:f-free-hard-always FPT [ 15 ] WC DAG W[1]-hard \cref cor:dag_out_k+t ? \alpha -Bounded Subgraph FPT \cref thm:alpha_bounded_fpt FPT \cref thm:alpha_bounded_total Strongly Connected Subgraph ? FPT \cref cor:scc_algo Clique FPT in time 1.6181^{k}n^{\mathcal{O}(1)} \cref thm:clique_better Table 1: Our main results for directed and undirected problems. WC stands for weakly connected, \propOp is an arbitrary, polynomial-time verifiable property. All FPT results are with respect to parameter k and all hardness results are with respect to parameter k+w . The problems corresponding to columns marked with (?) are open. For any property \propOp , we formulate our general problem as follows. Notice that in-secluded and out-secluded are equivalent for all properties that are invariant under the transposition of the edges. For this reason, we mostly focus on total-neighborhood and out-neighborhood. X-Secluded \propOp -Subgraph ( \text{X}\in\left\{\text{In},\text{Out},\text{Total}\right\} ) Parameter: An integer k\in\mathbb{N} Input: A directed graph G with vertex weights \omega\colon V\to\mathbb{N} and an integer w\in\mathbb{N} Output: An X-secluded set S\subseteq\vOp({G}) of weight \omega(S)\geq w that satisfies \propOp , or report that none exists. Our Contribution In this subsection, we present the results we obtained for the problem. See \Cref tab:our_results for an overview of the results we obtained in this paper. Strongly Connected Subgraph. We show that the Total-Secluded Strongly Connected Subgraph problem is fixed-parameter tractable when parameterized with k . Precisely, we prove the following result: Theorem 1 . Total-Secluded Strongly Connected Subgraph is solvable in time 2^{2^{2^{\mathcal{O}(k^{2})}}}n^{\mathcal{O}(1)} . We design our FPT algorithm for Total-Secluded Strongly Connected Subgraph problem using recursive understanding, a technique introduced by [ 12 ] and recently used successfully for various parameterized problems

Read the complete text