论文标题
边缘删除到类似树状的图形类
Edge deletion to tree-like graph classes
论文作者
论文摘要
对于固定属性（Graph class）$π$，给定图G和整数K，$π$ - 删除问题在于决定是否可以通过在最多$ k $ edges删除属性$π$的情况下将$ g $变成图形。 $π$ - 删除问题对于大多数良好的图形类别，例如弦，间隔，二分，平面，可比性和置换图等都是NP-HARD；甚至已知仙人掌的删除也是一般图的NP-HARD。但是，有一个值得注意的例外：树木的删除问题是多项式。在这一事实的激励下，我们研究了一些类似于树木的类别的删除问题，以这种方式解决文献中的知识差距。我们证明，即使输入是两部分图，对仙人掌的缺失也很难。从积极的一面来看，我们表明当输入是和弦时，问题就可以解决，对于准阈值图的特殊情况，我们给出了更简单，更快的算法。此外，我们在图类别$π$上提供了足够的结构条件，这意味着$π$ - 删除问题的NP硬度，并表明从一般图到森林的某些众所周知的森林子类缺失是NP-HARD。
For a fixed property (graph class) $Π$, given a graph G and an integer k, the $Π$-deletion problem consists in deciding if we can turn $G$ into a graph with the property $Π$ by deleting at most $k$ edges. The $Π$-deletion problem is known to be NP-hard for most of the well-studied graph classes, such as chordal, interval, bipartite, planar, comparability and permutation graphs, among others; even deletion to cacti is known to be NP-hard for general graphs. However, there is a notable exception: the deletion problem to trees is polynomial. Motivated by this fact, we study the deletion problem for some classes similar to trees, addressing in this way a knowledge gap in the literature. We prove that deletion to cacti is hard even when the input is a bipartite graph. On the positive side, we show that the problem becomes tractable when the input is chordal, and for the special case of quasi-threshold graphs we give a simpler and faster algorithm. In addition, we present sufficient structural conditions on the graph class $Π$ that imply the NP-hardness of the $Π$-deletion problem, and show that deletion from general graphs to some well-known subclasses of forests is NP-hard.
