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