Linear Kernels and Linear-Time Algorithms for Finding Large Cuts
Linear Kernels and Linear-Time Algorithms for Finding Large Cuts
复制标题
DOI：
10.1007/s00453-017-0388-z
复制
发表时间：
2017-10
期刊：
影响因子：
1.1
通讯作者：
M. Etscheid;Matthias Mnich
中科院分区：
文献类型：
--
作者：
M. Etscheid;Matthias Mnich
图的最大割问题及其推广是一个基本的组合问题。这些切割问题中的几个最近被证明是固定参数易处理的，并且当参数化高于由图的大小和顺序测量的紧下限时，允许多项式核。在本文中，我们继续这条线的研究，并大大提高了这些结果：我们表明，Crowston等人的算法。（Phenomica 72（3）：734 - 757，2015）的（Signed）Max-Cut Above Edwards − Erdos Boundd可以实现为线性时间运行;这显着改善了以前的分析与运行时间。我们给出了（Signed）Max-Cut Above Edwards − Erdos Boundd的渐近最优内核，具有O（k）个顶点，改进了Crowston等人的核。（Theor Comput Sci 513：53 - 64，2013）。我们改进了所有已知的用于强可扩展属性以上参数化的内核（a generalization of theMax-Cutresults）by Crowston et al.（Proceedings of FSTTCS 2013，Leibniz international proceedings in informatics，古瓦哈蒂，2013）从顶点到O（k）顶点，因此参数化在Poljak-Turzík界以上的Max无环子有向图存在一个O（k）顶点的核，并且可以及时求解;这回答了Crowston等人的未决问题（Proceedings of FSTTCS 2012，Leibniz international proceedings in informatics，Hyderabad，2012）。
The maximum cut problem in graphs and its generalizations are fundamental combinatorial problems. Several of these cut problems were recently shown to be fixed-parameter tractable and admit polynomial kernels when parameterized above the tight lower bound measured by the size and order of the graph. In this paper we continue this line of research and considerably improve several of those results:We show that an algorithm by Crowston et al. (Algorithmica 72(3):734–757, 2015) for(Signed) Max-Cut Above Edwards−Erdős Boundcan be implemented so as to run inlinear time; this significantly improves the previous analysis with run time.We give anasymptotically optimalkernel for(Signed) Max-Cut Above Edwards−Erdős BoundwithO(k) vertices, improving a kernel withvertices by Crowston et al. (Theor Comput Sci 513:53–64, 2013).We improveallknown kernels for parameterizations above strongly-extendible properties (a generalization of theMax-Cutresults) by Crowston et al. (Proceedings of FSTTCS 2013, Leibniz international proceedings in informatics, Guwahati, 2013) fromvertices toO(k) vertices.Therefore,Max Acyclic Subdigraphparameterized above Poljak–Turzík bound admits a kernel withO(k) vertices and can be solved intime; this answers an open question by Crowston et al. (Proceedings of FSTTCS 2012, Leibniz international proceedings in informatics, Hyderabad, 2012).All presented kernels can be computed in timeO(km).