## RenĂ© van Bevern, Vincent Froese, and Christian Komusiewicz.
Parameterizing edge modification problems above lower bounds.
*Theory of Computing Systems*, 62(3):739–770, 2018.
CSR'16 special issue.

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.*