论文标题
关于网格收缩的参数化复杂性
On the Parameterized Complexity Of Grid Contraction
论文作者
论文摘要
对于一个图$ \ Mathcal {g} $的家庭，$ \ Mathcal {g} $ - \ textsc {contractraction}问题作为输入图$ g $和一个整数$ k $，目标是确定是否存在$ f \ subseteq e（g subseteq e（g）$ k $ g/f $ g/f $ g/f $ f \ subseteq e（g）$ g/f。在这里，$ g/f $是通过$ f $收缩所有边缘从$ g $获得的图表。在本文中，我们从参数化的复杂性的角度启动\ textsc {网格收缩}的研究。我们提出了一个固定的参数可处理算法，在时间$ c^k \ cdot | v（g）|^{\ Mathcal {o}（1）} $的时间内运行。我们通过证明除非失败，否则对于\ textsc {grid收缩}没有运行时间$ c^{o（k）} \ cdot | v（g）|^{\ mathcal {o}（o}（1）} $，我们可以补充这一结果。我们还为此问题提供了多项式内核。
For a family of graphs $\mathcal{G}$, the $\mathcal{G}$-\textsc{Contraction} problem takes as an input a graph $G$ and an integer $k$, and the goal is to decide if there exists $F \subseteq E(G)$ of size at most $k$ such that $G/F$ belongs to $\mathcal{G}$. Here, $G/F$ is the graph obtained from $G$ by contracting all the edges in $F$. In this article, we initiate the study of \textsc{Grid Contraction} from the parameterized complexity point of view. We present a fixed parameter tractable algorithm, running in time $c^k \cdot |V(G)|^{\mathcal{O}(1)}$, for this problem. We complement this result by proving that unless Ð fails, there is no algorithm for \textsc{Grid Contraction} with running time $c^{o(k)} \cdot |V(G)|^{\mathcal{O}(1)}$. We also present a polynomial kernel for this problem.
