English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The celebrated notion of important separators bounds the number of small$(S,T)$-separators in a graph which are 'farthest from $S$' in a technicalsense. In this paper, we introduce a generalization of this powerfulalgorithmic primitive that is phrased in terms of $k$-secluded vertex sets:sets with an open neighborhood of size at most $k$.  In this terminology, the bound on important separators says that there are atmost $4^k$ maximal $k$-secluded connected vertex sets $C$ containing $S$ butdisjoint from $T$. We generalize this statement significantly: even when wedemand that $G[C]$ avoids a finite set $\mathcal{F}$ of forbidden inducedsubgraphs, the number of such maximal subgraphs is $2^{O(k)}$ and they can beenumerated efficiently. This allows us to make significant improvements for twoproblems from the literature.  Our first application concerns the 'Connected $k$-Secluded $\mathcal{F}$-freesubgraph' problem, where $\mathcal{F}$ is a finite set of forbidden inducedsubgraphs. Given a graph in which each vertex has a positive integer weight,the problem asks to find a maximum-weight connected $k$-secluded vertex set $C\subseteq V(G)$ such that $G[C]$ does not contain an induced subgraphisomorphic to any $F \in \mathcal{F}$. The parameterization by $k$ is known tobe solvable in triple-exponential time via the technique of recursiveunderstanding, which we improve to single-exponential.  Our second application concerns the deletion problem to scattered graphclasses. Here, the task is to find a vertex set of size at most $k$ whoseremoval yields a graph whose each connected component belongs to one of theprescribed graph classes $\Pi_1, \ldots, \Pi_d$. We obtain a single-exponentialalgorithm whenever each class $\Pi_i$ is characterized by a finite number offorbidden induced subgraphs. This generalizes and improves upon earlier resultsin the literature.

Single-Exponential FPT Algorithms for Enumerating Secluded $\mathcal{F}$-Free Subgraphs and Deleting to Scattered Graph Classes