Parameterizing Edge Modification Problems Above Lower Bounds

摘要

Abstract We study the parameterized complexity of a variant of the F - free Editing problem: Given a graph G and a natural number k , is it possible to modify at most k edges in G so that the resulting graph contains no induced subgraph isomorphic to F ? In our variant, the input additionally contains a vertex-disjoint packing ℋ $mathcal {H}$ of induced subgraphs of G , which provides a lower bound h ( ℋ ) $h(mathcal {H})$ on the number of edge modifications required to transform G into an F -free graph. While earlier works used the number k as parameter or structural parameters of the input graph G , we consider instead the parameter ℓ : = k − h ( ℋ ) $ell :=k-h(mathcal {H})$ , that is, the number of edge modifications above the lower bound h ( ℋ ) $h(mathcal {H})$ . We develop a framework of generic data reduction rules to show fixed-parameter tractability with respect to ℓ for K ~(3)- Free Editing , Feedback Arc Set in Tournaments , and Cluster Editing when the packing ℋ $mathcal {H}$ contains subgraphs with bounded solution size. For K ~(3)- Free Editing , we also prove NP-hardness in case of edge-disjoint packings of K ~(3)s and ℓ = 0, while for K ~( q )- Free Editing and q ≥ 6, NP-hardness for ℓ = 0 even holds for vertex-disjoint packings of K ~( q )s. In addition, we provide NP-hardness results for F - free Vertex Deletion , were the aim is to delete a minimum number of vertices to make the input graph F -free.