René van Bevern, Vincent Froese, and Christian Komusiewicz. Parameterizing edge modification problems above lower bounds. Theory of Computing Systems, 2017. CSR'16 special issue. In press.

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 H of induced subgraphs of G, which provides a lower bound h(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 l:=k-h(H), that is, the number of edge modifications above the lower bound h(H). We develop a framework of generic data reduction rules to show fixed-parameter tractability with respect to l for K_3-Free Editing, Feedback Arc Set in Tournaments, and Cluster Editing when the packing 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_3s and l=0, while for K_q-Free Editing and qge 6, NP-hardness for l=0 even holds for vertex-disjoint packings of K_qs. 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.

bib | DOI | slides | http ] Back


This file was generated by bibtex2html 1.98.