Cycles to the Rescue! Novel Constraints to Compute Maximum Planar Subgraphs Fast
Cycles to the Rescue! Novel Constraints to Compute Maximum Planar Subgraphs Fast
复制标题
DOI：
10.4230/lipics.esa.2018.19
复制
发表时间：
2018-06
期刊：
影响因子：
--
通讯作者：
Markus Chimani;Tilo Wiedera
中科院分区：
文献类型：
--
作者：
Markus Chimani;Tilo Wiedera
NP-hard最大平面子图问题要求给定图$G$的平面子图$H$使得$H$具有最大的边基数。二十多年来，唯一已知的非平凡精确算法是基于整数线性规划和库拉托夫斯基著名的平面性准则。我们在此方法的基础上，提出了新的约束类，以及多面体的提升，以获得可证明的更强的lp -松弛，从而在实践中更快的算法。新的约束以欧拉多面体公式为出发点，并结合考虑$G$中的循环。本文从理论和实践两个方面探讨了这一加强。
The NP-hard Maximum Planar Subgraph problem asks for a planar subgraph $H$ of a given graph $G$ such that $H$ has maximum edge cardinality. For more than two decades, the only known non-trivial exact algorithm was based on integer linear programming and Kuratowski's famous planarity criterion. We build upon this approach and present new constraint classes, together with a lifting of the polyhedron, to obtain provably stronger LP-relaxations, and in turn faster algorithms in practice. The new constraints take Euler's polyhedron formula as a starting point and combine it with considering cycles in $G$. This paper discusses both the theoretical as well as the practical sides of this strengthening.