Vertex Deletion into Bipartite Permutation Graphs.

A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines and , 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 -vertex graph, whether we can remove at most vertices to obtain a bipartite permutation graph.

Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs.

Let and be hereditary graph classes. Consider the following problem: given a graph , find a largest, in terms of the number of vertices, induced subgraph of that belongs to . We prove that it can be solved in time, where is the number of vertices of , if the following conditions are satisfied:the graphs in are sparse, i.