论文标题
顶点删除到两部分置换图中
Vertex deletion into bipartite permutation graphs
论文作者
论文摘要
置换图可以定义为段落的交点图，其端点位于两个平行线$ l_1 $和$ l_2 $上，每个线上一个。双分置置换率图是一个置换图，是两部分。在本文中，我们研究了两分置换顶点缺失问题的参数化复杂性，该问题询问给定的N-Vertex图，我们是否可以在大多数k顶点上删除以获得双分部分置换图。刘易斯和Yannakakis的经典结果是NP完整的。我们分析了所谓的几乎两部分排列图的结构，这些图可能包含孔（大型诱导循环）与双分部分置换图相比。我们利用此图中最短孔的结构特性。我们使用它来获得用于运行时间$ O（9^k \ cdot n^9）$的二分置换顶点删除问题的算法，并且还提供了一个多项式时间9- approximation算法。
A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines $l_1$ and $l_2$, one on each. A bipartite permutation graph is a permutation graph which is bipartite. In this paper we study the parameterized complexity of the bipartite permutation vertex deletion problem, which asks, for a given n-vertex graph, whether we can remove at most k vertices to obtain a bipartite permutation graph. This problem is NP-complete by the classical result of Lewis and Yannakakis. We analyze the structure of the so-called almost bipartite permutation graphs which may contain holes (large induced cycles) in contrast to bipartite permutation graphs. We exploit the structural properties of the shortest hole in a such graph. We use it to obtain an algorithm for the bipartite permutation vertex deletion problem with running time $O(9^k\cdot n^9)$, and also give a polynomial-time 9-approximation algorithm.
