论文标题
朝弦 /远距离遗传性顶点缺失的恒定因子近似
Towards constant-factor approximation for chordal / distance-hereditary vertex deletion
论文作者
论文摘要
对于一个图$ \ MATHCAL {F} $的家庭，加权$ \ Mathcal {f} $ - 删除是输入是顶点加权图$ g =（v，e）$的问题，目标是删除$ s \ subseteq v $具有最小$ g \ g \ setMinus s $ nsminus s \ n \ n \ sepminus s \ n \ n.为完美图的大型子类设计一种恒定因素近似算法是一个有趣的研究方向。已知块图，3叶功率图和间隔图可以允许恒定因子近似算法，但问题对于弦图和远距离式图形开放。 在本文中，我们通过在$ f $是弦图和远距离标记图的相交时提出恒定因素近似算法来在此列表中添加一个类。它们被称为托勒密图，并形成上面的块图和3叶功率图的超集。我们的证明介绍了新的属性和算法结果，这些属性是相互关系的挖掘图，以及用于利用这种关系的反馈顶点集的近似算法（命名为具有先验约束的反馈顶点集），每种关系都可能具有独立的关注。
For a family of graphs $\mathcal{F}$, Weighted $\mathcal{F}$-Deletion is the problem for which the input is a vertex weighted graph $G=(V,E)$ and the goal is to delete $S\subseteq V$ with minimum weight such that $G\setminus S\in\mathcal{F}$. Designing a constant-factor approximation algorithm for large subclasses of perfect graphs has been an interesting research direction. Block graphs, 3-leaf power graphs, and interval graphs are known to admit constant-factor approximation algorithms, but the question is open for chordal graphs and distance-hereditary graphs. In this paper, we add one more class to this list by presenting a constant-factor approximation algorithm when $F$ is the intersection of chordal graphs and distance-hereditary graphs. They are known as ptolemaic graphs and form a superset of both block graphs and 3-leaf power graphs above. Our proof presents new properties and algorithmic results on inter-clique digraphs as well as an approximation algorithm for a variant of Feedback Vertex Set that exploits this relationship (named Feedback Vertex Set with Precedence Constraints), each of which may be of independent interest.
