Parameterized Algorithms for Zero Extension and Metric Labelling Problems
Parameterized Algorithms for Zero Extension and Metric Labelling Problems
复制标题
DOI：
10.4230/lipics.icalp.2018.94
复制
发表时间：
2018-02
影响因子：
2.1
通讯作者：
F. Reidl;Magnus Wahlström
中科院分区：
文献类型：
--
作者：
F. Reidl;Magnus Wahlström
研究了参数化复杂度范式下的零扩展和度量标记问题。这些都是自然的、经过充分研究的问题，具有重要的应用程序，但以前没有受到参数化复杂性的太多关注。根据所选择的成本函数$\mu$，我们发现不同的算法方法可以应用于设计fpt算法：对于任意$\mu$，我们通过穿过切割的边的数量（而不是成本）进行参数化，并展示如何使用随机收缩在时间上解决ZERO EXTENSION $O(|D|^{O(k^2)} n^4 \log n)$。在$\mu$是度量的情况下，我们将参数和输入大小的运行时间都提高到$O(|D|^{O(k)} m)$。我们进一步证明了该问题允许多项式稀疏化，即一个大小为$O(k^{|D|+1})$的核，它独立于度量$\mu$。在更强的条件下，$\mu$是由树中叶子的距离描述的，我们通过真正解决方案的成本$q$和“离散松弛”$p$之间的间隙参数$(q - p)$来参数化，并实现运行时间$O(|D|^{q-p} |T|m + |T|\phi(n,m))$，其中$T$是定义$\mu$的树的大小，$\phi(n,m)$是最大流量计算的运行时间。我们为更一般的度量标记实现了类似的运行，同时还允许$\mu$使用vcsp理论中的工具作为树中任意节点子集之间的距离度量。我们期望后一个结果中使用的方法有进一步的应用。
We consider the problems ZERO EXTENSION and METRIC LABELLING under the paradigm of parameterized complexity. These are natural, well-studied problems with important applications, but have previously not received much attention from parameterized complexity. Depending on the chosen cost function $\mu$, we find that different algorithmic approaches can be applied to design FPT-algorithms: for arbitrary $\mu$ we parameterized by the number of edges that cross the cut (not the cost) and show how to solve ZERO EXTENSION in time $O(|D|^{O(k^2)} n^4 \log n)$ using randomized contractions. We improve this running time with respect to both parameter and input size to $O(|D|^{O(k)} m)$ in the case where $\mu$ is a metric. We further show that the problem admits a polynomial sparsifier, that is, a kernel of size $O(k^{|D|+1})$ that is independent of the metric $\mu$. With the stronger condition that $\mu$ is described by the distances of leaves in a tree, we parameterize by a gap parameter $(q - p)$ between the cost of a true solution $q$ and a `discrete relaxation' $p$ and achieve a running time of $O(|D|^{q-p} |T|m + |T|\phi(n,m))$ where $T$ is the size of the tree over which $\mu$ is defined and $\phi(n,m)$ is the running time of a max-flow computation. We achieve a similar running for the more general METRIC LABELLING, while also allowing $\mu$ to be the distance metric between an arbitrary subset of nodes in a tree using tools from the theory of VCSPs. We expect the methods used in the latter result to have further applications.