论文标题
关于\ textsc {最大程度收缩}的参数化复杂性问题
On the Parameterized Complexity of \textsc{Maximum Degree Contraction} Problem
论文作者
论文摘要
在\ textsc {最大学位收缩}问题中，输入是$ n $ vertices上的图$ g $，而整数$ k，d $，目的是检查$ g $是否可以最多最多使用$ d $的最高图，最多使用$ k $ edge Edge Crossions。一种简单的蛮力算法，该算法检查解决方案的所有可能的边缘集$ n^{\ Mathcal {o}（k）} $。作为我们的第一个结果，我们证明该算法在指数时间假设（ð）下是渐近的最佳，最佳的指数中的常数。 Belmonte，Golovach，Van't Hof和Paulusma在参数化的复杂性领域研究了问题，并证明了它承认它在时间$ $ $（D + K）^{2K} {2K} \ cdot n^{\ cdot N^{\ Mathcal {\ Mathcal {O} {O} {o} {o}（1）} = 2^2^{ （k+d））}} \ cdot n^{\ Mathcal {o}（1）} $，并且对于每个常数$ d \ ge 2 $（acta Informatica $（2014）$）保留\ np-hard。我们提出了一个不同的\ fpt \ algorithm，该算法$ 2^{\ MATHCAL {o}（dk）} \ CDOT N^{\ MATHCAL {O}（O}（1）} $。特别是，对于每个固定的$ d $，我们的算法在时间上运行$ 2^{\ Mathcal {o}（k）} \ cdot n^{\ Mathcal {o}（1）} $。在同一篇文章中，作者询问问题是否在由$ k + d $参数化时是否允许多项式内核。我们以否定态回答这个问题，并证明除非$ \ np \ subseteq \ conp/poly $，否则它不接受多项式压缩。
In the \textsc{Maximum Degree Contraction} problem, input is a graph $G$ on $n$ vertices, and integers $k, d$, and the objective is to check whether $G$ can be transformed into a graph of maximum degree at most $d$, using at most $k$ edge contractions. A simple brute-force algorithm that checks all possible sets of edges for a solution runs in time $n^{\mathcal{O}(k)}$. As our first result, we prove that this algorithm is asymptotically optimal, upto constants in the exponents, under Exponential Time Hypothesis (Ð). Belmonte, Golovach, van't Hof, and Paulusma studied the problem in the realm of Parameterized Complexity and proved, among other things, that it admits an \FPT\ algorithm running in time $(d + k)^{2k} \cdot n^{\mathcal{O}(1)} = 2^{\mathcal{O}(k \log (k+d) )} \cdot n^{\mathcal{O}(1)}$, and remains \NP-hard for every constant $d \ge 2$ (Acta Informatica $(2014)$). We present a different \FPT\ algorithm that runs in time $2^{\mathcal{O}(dk)} \cdot n^{\mathcal{O}(1)}$. In particular, our algorithm runs in time $2^{\mathcal{O}(k)} \cdot n^{\mathcal{O}(1)}$, for every fixed $d$. In the same article, the authors asked whether the problem admits a polynomial kernel, when parameterized by $k + d$. We answer this question in the negative and prove that it does not admit a polynomial compression unless $\NP \subseteq \coNP/poly$.
