论文标题
次要封闭图类别的K-apices。 ii。参数化算法
k-apices of minor-closed graph classes. II. Parameterized algorithms
论文作者
论文摘要
令$ {\ cal g} $为次要的图形类。我们说，如果$ {\ cal g} $ a Graph $ g $是$ k $ -apex，如果$ g $包含最多$ k $ vertices的$ s $，则$ g \ setminus s $属于$ {\ cal g} $。我们用$ {\ cal a} _k（{\ cal g}）$表示$ {\ cal g}的$ k $ - apices的集合。在本文中，我们提供的算法在本文中不属于$ {\ cal a} _k（{\ cal g}）。我们提供了一种算法，在$ n $ vertices上给定图形$ g $，以$ 2^{{\ sf poly}（k poly}（k）（k）} \ cdot n^3 $ - cal $ g cal cal s in n $ n $ vertices in $ 2^{{\ sf poly}（k） a} _k（{\ cal g}）$，或报告$ g \ notin {\ cal a} _k（{\ cal g}）$。这里$ {\ sf poly} $是一个多项式函数，其程度取决于$ {\ cal g}的最大尺寸。
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 such that $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 of this series we obtained upper bounds on the size of the graphs in the minor-obstruction set of ${\cal A}_k ({\cal G})$, i.e., the minor-minimal set of graphs not belonging to ${\cal A}_k ({\cal G}).$ In this article we provide an algorithm that, given a graph $G$ on $n$ vertices, runs in $2^{{\sf poly}(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 size of 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 running in $2^{{\sf poly}(k)}\cdot n^2$-time.
