论文标题
工程精确的准阈值编辑
Engineering Exact Quasi-Threshold Editing
论文作者
论文摘要
准阈值图是$ \ {C_4，P_4 \} $ - 免费图形，即它们不包含四个节点的任何周期或路径作为诱导子图。我们研究$ \ {C_4，P_4 \} $ - 免费编辑问题，这是找到最小数量的边缘插入或删除以将输入图转换为准阈值图的问题。这个问题是通过使用分支和结合算法在编辑数量中的NP-硬质，但可固定参数可处理（FPT），并接受简单的整数线性编程公式（ILP）。这两种方法还适用于任何有限的图表$ f $的一般$ f $ F $ FRE-FR-FRE编辑问题。对于FPT算法，我们引入了一种快速的启发式方法，用于计算高质量的下限和改进的分支策略。对于ILP，我们设计了行生成的几种变体。我们在大量蛋白质相似性图上评估了准阈值编辑的两种方法。在大多数情况下，我们的优化将FPT算法加快了一到三个数量级。我们使用Gurobi解决的ILP的运行时间仅略快。通过所有优化，即使列出了所有解决方案，FPT算法也比ILP稍快。此外，我们表明，对于几乎所有图形，先前提出的准阈值编辑启发式QTM的解决方案都接近最佳。
Quasi-threshold graphs are $\{C_4, P_4\}$-free graphs, i.e., they do not contain any cycle or path of four nodes as an induced subgraph. We study the $\{C_4, P_4\}$-free editing problem, which is the problem of finding a minimum number of edge insertions or deletions to transform an input graph into a quasi-threshold graph. This problem is NP-hard but fixed-parameter tractable (FPT) in the number of edits by using a branch-and-bound algorithm and admits a simple integer linear programming formulation (ILP). Both methods are also applicable to the general $F$-free editing problem for any finite set of graphs $F$. For the FPT algorithm, we introduce a fast heuristic for computing high-quality lower bounds and an improved branching strategy. For the ILP, we engineer several variants of row generation. We evaluate both methods for quasi-threshold editing on a large set of protein similarity graphs. For most instances, our optimizations speed up the FPT algorithm by one to three orders of magnitude. The running time of the ILP, that we solve using Gurobi, becomes only slightly faster. With all optimizations, the FPT algorithm is slightly faster than the ILP, even when listing all solutions. Additionally, we show that for almost all graphs, solutions of the previously proposed quasi-threshold editing heuristic QTM are close to optimal.
