ABSTRACT
A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines â 1 and â 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 [20]. 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 · n 9 ) , and also give a polynomial-time 9-approximation algorithm.
ABSTRACT
Let C and D be hereditary graph classes. Consider the following problem: given a graph G ∈ D , find a largest, in terms of the number of vertices, induced subgraph of G that belongs to C . We prove that it can be solved in 2 o ( n ) time, where n is the number of vertices of G, if the following conditions are satisfied:the graphs in C are sparse, i.e., they have linearly many edges in terms of the number of vertices;the graphs in D admit balanced separators of size governed by their density, e.g., O ( Δ ) or O ( m ) , where Δ and m denote the maximum degree and the number of edges, respectively; andthe considered problem admits a single-exponential fixed-parameter algorithm when parameterized by the treewidth of the input graph. This leads, for example, to the following corollaries for specific classes C and D :a largest induced forest in a P t -free graph can be found in 2 O ~ ( n 2 / 3 ) time, for every fixed t; anda largest induced planar graph in a string graph can be found in 2 O ~ ( n 2 / 3 ) time.
