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/

Zendy Plus

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

Zendy Tools

Zendy Open

Let ${\cal G}$ be a minor-closed graph class. We say that a graph $G$ is a$k$-apex of ${\cal G}$ if $G$ contains a set $S$ of at most $k$ vertices suchthat $G\setminus S$ belongs to ${\cal G}$. We denote by ${\cal A}_k ({\cal G})$the set of all graphs that are $k$-apices of ${\cal G}.$ In the first paper ofthis series we obtained upper bounds on the size of the graphs in theminor-obstruction set of ${\cal A}_k ({\cal G})$, i.e., the minor-minimal setof graphs not belonging to ${\cal A}_k ({\cal G}).$ In this article we providean algorithm that, given a graph $G$ on $n$ vertices, runs in $2^{{\sfpoly}(k)}\cdot n^3$-time and either returns a set $S$ certifying that $G \in{\cal A}_k ({\cal G})$, or reports that $G \notin {\cal A}_k ({\cal G})$. Here${\sf poly}$ is a polynomial function whose degree depends on the maximum sizeof a minor-obstruction of ${\cal G}.$ In the special case where ${\cal G}$excludes some apex graph as a minor, we give an alternative algorithm runningin $2^{{\sf poly}(k)}\cdot n^2$-time.

k-apices of minor-closed graph classes. II. Parameterized algorithms