FPT Algorithms to Compute the Elimination Distance to Bipartite Graphs and More
share
For a hereditary graph class ℋ, the ℋ-elimination distance of a graph G is the minimum number of rounds needed to reduce G to a member of ℋ by removing one vertex from each connected component in each round. The ℋ-treewidth of a graph G is the minimum, taken over all vertex sets X for which each connected component of G - X belongs to ℋ, of the treewidth of the graph obtained from G by replacing the neighborhood of each component of G-X by a clique and then removing V(G) ∖ X. These parameterizations recently attracted interest because they are simultaneously smaller than the graph-complexity measures treedepth and treewidth, respectively, and the vertex-deletion distance to ℋ. For the class ℋ of bipartite graphs, we present non-uniform fixed-parameter tractable algorithms for testing whether the ℋ-elimination distance or ℋ-treewidth of a graph is at most k. Along the way, we also provide such algorithms for all graph classes ℋ defined by a finite set of forbidden induced subgraphs.
READ FULL TEXT