## 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 ℋ of induced subgraphs of G, which provides a lower bound 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(ℋ) , that is, the number of edge modifications above the lower bound 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 ℋ 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.

Original language | English |
---|---|

Pages (from-to) | 739-770 |

Number of pages | 32 |

Journal | Theory of Computing Systems |

Volume | 62 |

Issue number | 3 |

DOIs | |

Publication status | Published - 1 Apr 2018 |

## Keywords

- Cluster editing
- Feedback arc set
- Fixed-parameter algorithm
- Graph-based Clustering
- Kernelization
- NP-hard problem
- Subgraph packing
- FEEDBACK SET PROBLEMS
- ALGORITHMS
- TRACTABILITY
- KERNELS