论文标题
打破障碍物$ 2^k $，用于弦图中的子集反馈顶点
Breaking the Barrier $2^k$ for Subset Feedback Vertex Set in Chordal Graphs
论文作者
论文摘要
子集反馈顶点集问题（SFVS），要从给定的图中删除$ k $的顶点，以使顶点子集中的任何顶点（称为终端集）在其余图中不在周期中，概括了著名的反馈顶点设置问题和多路切割问题。即使在拆分图和和弦图中，SFV仍然保持NP-HARD，弦图中的SFV（SFVS-C）可以被视为隐式的3击集问题。但是，比三击集更快地解决SFVS-C并不容易。在2019年，菲利普，拉扬，索拉布和故事（Algorithmica 2019）证明，可以用$ \ nathcal {o}^{*} {*}（2^{k}）$解决SFVS-C，稍微改善了最佳结果$ \ \ \ \ \ \ \ \ \ {o}^{o}^{2.076^$ {k.在本文中，我们通过给出了$ \ Mathcal {o}^{*}（1.820^{k}）$ - 时间算法，打破了SFVS-C的“ $ 2^{k} $ - 障碍”。我们的算法使用基于dulmage-mendelsohn分解和分裂和串扰方法的减少和分支规则。
The Subset Feedback Vertex Set problem (SFVS), to delete $k$ vertices from a given graph such that any vertex in a vertex subset (called a terminal set) is not in a cycle in the remaining graph, generalizes the famous Feedback Vertex Set problem and Multiway Cut problem. SFVS remains NP-hard even in split and chordal graphs, and SFVS in Chordal Graphs (SFVS-C) can be considered as an implicit 3-Hitting Set problem. However, it is not easy to solve SFVS-C faster than 3-Hitting Set. In 2019, Philip, Rajan, Saurabh, and Tale (Algorithmica 2019) proved that SFVS-C can be solved in $\mathcal{O}^{*}(2^{k})$ time, slightly improving the best result $\mathcal{O}^{*}(2.076^{k})$ for 3-Hitting Set. In this paper, we break the "$2^{k}$-barrier" for SFVS-C by giving an $\mathcal{O}^{*}(1.820^{k})$-time algorithm. Our algorithm uses reduction and branching rules based on the Dulmage-Mendelsohn decomposition and a divide-and-conquer method.
