论文标题
反馈集的紧密本地化
Tight Localizations of Feedback Sets
论文作者
论文摘要
经典的NP-HARD反馈弧设置问题（FASP）和反馈顶点集问题（FVSP）要求最低集弧$ \ varepsilon \ subseteq e $ $或vertices $ c $ν\ subseteq v $，其删除$ g g \ g \ setMinus \ varepsilon $ g \ g \ g \ g \ g \ g \ seT $ $ g =（v，e）$ cyclic。尽管已知这两个问题都是APX，但近似算法或不合适性的证据尚不清楚。我们提出了一个新的$ \ Mathcal {O}（| V || e |^4）$ - 定向FASP的启发式。虽然已知$ r \ 1.3606 $的比率是APX硬度的下限，至少通过经验验证，我们达到了$ r \ leq 2 $的近似值。最相关的应用程序，例如电路测试，要求在大型稀疏图上求解FASP，由于我们的方法，可以在紧密的误差范围内有效地完成。
The classical NP-hard feedback arc set problem (FASP) and feedback vertex set problem (FVSP) ask for a minimum set of arcs $\varepsilon \subseteq E$ or vertices $ν\subseteq V$ whose removal $G\setminus \varepsilon$, $G\setminus ν$ makes a given multi-digraph $G=(V,E)$ acyclic, respectively. Though both problems are known to be APX-hard, approximation algorithms or proofs of inapproximability are unknown. We propose a new $\mathcal{O}(|V||E|^4)$-heuristic for the directed FASP. While a ratio of $r \approx 1.3606$ is known to be a lower bound for the APX-hardness, at least by empirical validation we achieve an approximation of $r \leq 2$. The most relevant applications, such as circuit testing, ask for solving the FASP on large sparse graphs, which can be done efficiently within tight error bounds due to our approach.
