Approximation algorithms for connected maximum cut and related problems
Approximation algorithms for connected maximum cut and related problems
复制标题
连通最大割的近似算法及相关问题
DOI：
10.1016/j.tcs.2020.01.016
复制
发表时间：
2020
影响因子：
1.1
通讯作者：
Sarpatwar, Kanthi
中科院分区：
文献类型：
--
作者：
Hajiaghayi, MohammadTaghi;Kortsarz, Guy;MacDavid, Robert;Purohit, Manish;Sarpatwar, Kanthi
连通最大割问题的一个实例由无向图G=（V，E）组成，目标是找到顶点子集S V，使割δ（S）中的边数最大化，使得诱导图G [S]是连通的。我们提出了第一个非平凡的Ω（1 log n）近似算法的连通最大割问题在一般图使用新的技术。然后，我们将我们的算法扩展到边加权的情况下，得到一个多对数近似算法。有趣的是，在经典的最大割问题，可以解决在多项式时间的平面图，我们表明，连接最大割问题仍然是NP-难的加权，平面图。在积极的一面，我们得到了一个多项式时间近似计划的平面图和更一般的有界亏格图的连通最大割问题。
An instance of the Connected Maximum Cut problem consists of an undirected graph G=(V, E) and the goal is to find a subset of vertices S⊆ V that maximizes the number of edges in the cut δ (S) such that the induced graph G [S] is connected. We present the first non-trivial Ω (1 log n) approximation algorithm for the Connected Maximum Cut problem in general graphs using novel techniques. We then extend our algorithm to edge weighted case and obtain a poly-logarithmic approximation algorithm. Interestingly, in contrast to the classical Max-Cut problem that can be solved in polynomial time on planar graphs, we show that the Connected Maximum Cut problem remains NP-hard on unweighted, planar graphs. On the positive side, we obtain a polynomial time approximation scheme for the Connected Maximum Cut problem on planar graphs and more generally on bounded genus graphs.