论文标题
更快的参数化算法用于修改问题的次要类别
Faster parameterized algorithms for modification problems to minor-closed classes
论文作者
论文摘要
令$ {\ cal g} $为次要的图形类，让$ g $为$ n $ vertex图。我们说$ g $是$ k $ -apex的$ {\ cal g} $，如果$ g $包含最多$ k $ vertices的$ s $，则$ g \ setminus s $属于$ {\ cal g} $。我们的第一个结果是一种算法，该算法决定$ g $是否为$ k $ -apex的$ {\ cal g} $ in Time $ 2^{{\ sf poly}（k）} \ cdot n^2 $，其中$ {\ sf poly} $是polynomial函数，是$ polynomial函数，该功能取决于$ {\ cal g g} $。该算法改进了先前的算法，由Sau，Stamoulis和Thilikos [ICALP 2020]给出，其运行时间为$ 2^{{\ sf poly}（k）} \ cdot n^3 $。 $ g $至$ {\ cal g} $的消除距离是由$ {\ sf ed} _ {\ cal g}（g）$表示的，是将$ g $的每个连接组件减少到$ {\ cal g} $中的每个连接组件中所需的最低弹奏数量，从每个连接的组成部分中删除一个vertex。 Bulian and Dawar [Algorithmica 2017]提供了一个带有参数$ k $的fpt-algorithm，以决定是否$ {\ sf ed} _ {\ cal g}（g）\ leq k $。但是，它对$ k $的依赖并不明确。我们扩展了第一个算法中使用的技术来决定是否$ {\ sf ed} _ {\ cal g}（g）\ leq k $ in Time $ 2^{2^{2^{2^{{\ sf poly}}（k）}}}}}}}}}}}} \ cdot n^2 $。这是此问题的第一个算法，其中具有$ k $的显式参数依赖性。在特殊情况下，$ {\ cal g} $不包括一些辅助图作为未成年人，我们给出了两种替代算法，在时间上运行$ 2^{2^{{\ cal o}（k^2 \ log k）}}}}}} \ cdot n^2 $ and $ 2 $ and $ 2^$ and $ 2^$ c. $ {\ sf poly} $取决于$ {\ cal g} $。作为这些算法的垫脚石，我们提供了一种算法，该算法决定是否$ {\ sf ed} _ {\ cal g}（g）\ leq k $ in Time $ 2^{{\ cal o} {\ cal o}（{\ cal o}（{\ sf sf sf sf tw} \ cdot tw} \ cdot cd k+sf plog { $ {\ sf tw} $是$ g $的树宽。最后，我们在图形类别的次要尺寸集$ {\ cal e} _k（{\ cal g}）= \ {g \ iNd {\ sf ed} _ {\ cal g}（g g}（g leq k k \ k \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ^ $）中，我们提供了图形大小的明确上限。
Let ${\cal G}$ be a minor-closed graph class and let $G$ be an $n$-vertex graph. We say that $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}$. Our first result is an algorithm that decides whether $G$ is a $k$-apex of ${\cal G}$ in time $2^{{\sf poly}(k)}\cdot n^2$, where ${\sf poly}$ is a polynomial function depending on ${\cal G}$. This algorithm improves the previous one, given by Sau, Stamoulis, and Thilikos [ICALP 2020], whose running time was $2^{{\sf poly}(k)}\cdot n^3$. The elimination distance of $G$ to ${\cal G}$, denoted by ${\sf ed}_{\cal G}(G)$, is the minimum number of rounds required to reduce each connected component of $G$ to a graph in ${\cal G}$ by removing one vertex from each connected component in each round. Bulian and Dawar [Algorithmica 2017] provided an FPT-algorithm, with parameter $k$, to decide whether ${\sf ed}_{\cal G}(G)\leq k$. However, its dependence on $k$ is not explicit. We extend the techniques used in the first algorithm to decide whether ${\sf ed}_{\cal G}(G)\leq k$ in time $2^{2^{2^{{\sf poly}(k)}}}\cdot n^2$. This is the first algorithm for this problem with an explicit parametric dependence in $k$. In the special case where ${\cal G}$ excludes some apex-graph as a minor, we give two alternative algorithms, running in time $2^{2^{{\cal O}(k^2\log k)}}\cdot n^2$ and $2^{{\sf poly}(k)}\cdot n^3$ respectively, where $c$ and ${\sf poly}$ depend on ${\cal G}$. As a stepping stone for these algorithms, we provide an algorithm that decides whether ${\sf ed}_{\cal G}(G)\leq k$ in time $2^{{\cal O}({\sf tw}\cdot k+{\sf tw}\log{\sf tw})}\cdot n$, where ${\sf tw}$ is the treewidth of $G$. Finally, we provide explicit upper bounds on the size of the graphs in the minor-obstruction set of the class of graphs ${\cal E}_k({\cal G})=\{G\mid{\sf ed}_{\cal G}(G)\leq k\}$.
