论文标题
减少规则和ILP是您所需要的：最小的定向反馈顶点集
Reduction Rules and ILP Are All You Need: Minimal Directed Feedback Vertex Set
论文作者
论文摘要
本说明描述了作为2022年PACE竞争的一部分，用于最小的有向反馈顶点的精确求解器的开发。该求解器主要是通过积极地试图将DFV问题减少到最小的覆盖问题，并应用根据顶点覆盖文献所改编的减少规则来提供动力。使用SCIP将结果问题作为整数线性程序（ILP）解决。最终的求解器在竞争中表现出了第二好的，尽管提交时间的一个错误使它取消了资格。另外，我们描述了一个新的顶点盖还原，从而概括了桌面还原规则。
This note describes the development of an exact solver for Minimal Directed Feedback Vertex Set as part of the PACE 2022 competition. The solver is powered largely by aggressively trying to reduce the DFVS problem to a Minimal Cover problem, and applying reduction rules adapted from Vertex Cover literature. The resulting problem is solved as an Integer Linear Program (ILP) using SCIP. The resulting solver performed the second-best in the competition, although a bug at submission time disqualified it. As an additional note, we describe a new vertex cover reduction generalizing the Desk reduction rule.
