Outer-Planar Vertex Deletion on AT-Free Graphs
摘要
The \(\mathcal {F}\) -minor-free-deletion problem asks to find minimum number of vertices S in a given graph G such that \(G \setminus S\) does not contain any graph from the specified family \(\mathcal {F}\) as a minor. In this paper, we consider \(\{K_{2,3},K_4\}\) -minor-free-deletion problem in AT-free graphs, which is equivalent to finding a maximum induced outer-planar graph of a given AT-free graph. We show that this problem is solvable in polynomial-time. This problem can also be seen as a natural extension of minimum vertex cover and minimum feedback vertex set problem since they are equivalent to \(\{K_{2}\}\) and \(\{K_3\}\) minor free deletion problems respectively and are known to be polynomial time solvable in AT-free graphs [2, 24]. Additionally, we provide a polynomial-time algorithm for finding a maximum induced linear forest in AT-free graphs, which serves as a key subroutine in our algorithm to compute a maximum induced outer-planar graph.