Fine-Grained Algorithm Design for Matching
Fine-Grained Algorithm Design for Matching
复制标题
细粒度的匹配算法设计
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
R. Niedermeier
中科院分区：
文献类型：
--
作者：
G. B. Mertzios;A. Nichterlein;R. Niedermeier
在无向图中查找最大基数匹配可以说是最核心的图问题之一。对于 $m$ 边和 $n$ 顶点图，众所周知，它可以在 $O(msqrt{n})$ 时间内求解；然而，对于一些应用程序来说，这个运行时间仍然太慢。改善这个最坏情况的上限需要数十年的研究。在本文中，我们主要关注输入相对于几种琐碎距离的参数化，即输入距某些线性时间可解的情况有多远。我们的贡献是双重的。首先，我们关注线性时间固定参数算法（具有低多项式参数依赖性）。为此，我们开发了第一个线性时间算法，用于在可比图上进行最大匹配；该算法基于最近发现的词典深度优先搜索（LDFS）并且具有独立的意义。使用该算法，我们推导出一般图的 $O(k(n+m))$ 时间算法，其中 $k$ 是到可比图的顶点删除距离。其次，我们关注线性时间核化。我们开始对最大匹配问题的各种“琐碎距离”参数进行更深入、系统的研究。我们分别设计大小为 $O(k)$、$O(k^2)$、$O(k^3)$ 和 $2^{O(k)}$ 的线性（和几乎线性）时间可计算内核，其中 $k$ 是每种情况下考虑的参数。研究多项式时间可解问题的线性时间核化（例如最大匹配）会带来大量新的且组合有趣的挑战。根据我们的结果，我们假设最大匹配有明显的潜力成为“P 研究中的 FPT”的“果蝇”，类似于顶点覆盖在 NP 难问题的经典 FPT 研究中所发挥的开创性作用。
Finding maximum-cardinality matchings in undirected graphs is arguably one of the most central graph problems. For $m$-edge and $n$-vertex graphs, it is well-known to be solvable in $O(msqrt{n})$ time; however, for several applications this running time is still too slow. Improving this worst-case upper bound resisted decades of research. In this paper we mainly focus on parameterizations of the input with respect to several kinds of distance to triviality, i.e. how far is the input from some linear-time solvable cases. Our contribution is twofold. First we focus on linear-time fixed-parameter algorithms (with low polynomial parameter dependence). To this end we develop the first linear-time algorithm for maximum matching on cocomparability graphs; this algorithm is based on the recently discovered Lexicographic Depth First Search (LDFS) and is of independent interest. Using this algorithm we derive an $O(k(n+m))$-time algorithm for general graphs, where $k$ is the vertex deletion distance to cocomparability graphs. Second we focus on linear-time kernelization. We start a deeper and systematic study of various "distance to triviality"-parameters for the maximum matching problem. We design linear (and almost linear) time computable kernels of size $O(k)$, $O(k^2)$, $O(k^3)$, and $2^{O(k)}$, respectively, where $k$ is the considered parameter in each case. Investigating linear-time kernelization of a polynomial-time solvable problem, such as maximum matching, leads to a rich number of new and combinatorially interesting challenges. Based on our results, we postulate that maximum matching has the clear potential to become the "drosophila" of "FPT in P studies" analogously to the path-breaking role vertex covering played for classical FPT studies for NP-hard problems.