FPT Algorithms to Compute the Elimination Distance to Bipartite Graphs and More

Abstract

For a hereditary graph class $\mathcal{H}$, the $\mathcal{H}$-elimination distance of a graph $G$ is the minimum number of rounds needed to reduce $G$ to a member of $\mathcal{H}$ by removing one vertex from each connected component in each round. The $\mathcal{H}$-treewidth of a graph $G$ is the minimum, taken over all vertex sets $X$ for which each connected component of $G-X$ belongs to $\mathcal{H}$, 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)\setminus 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 $\mathcal{H}$. For the class $\mathcal{H}$ of bipartite graphs, we present non-uniform fixed-parameter tractable algorithms for testing whether the $\mathcal{H}$-elimination distance or $\mathcal{H}$-treewidth of a graph is at most $k$. Along the way, we also provide such algorithms for all graph classes $\mathcal{H}$ defined by a finite set of forbidden induced subgraphs.

14 pages, to appear at WG 2021