## René van Bevern, Vincent Froese, and Christian Komusiewicz.
Parameterizing edge modification problems above lower bounds.
In *Proceedings of the 11th International Computer Science
Symposium in Russia (CSR'16), St. Petersburg, Russian Federation*, volume
9691 of *Lecture Notes in Computer Science*, pages 57–72. Springer,
2016.
The final version of this article appeared in the CSR'16 special
issue of Theory of Computing Systems.

For a fixed graph F, 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 the
parameter l:=k-h(H) instead, that is, the number of
edge modifications above the lower bound h(H). We
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 modification
cost. For K3-Free Editing, we also prove NP-hardness
in case of edge-disjoint packings of K3s and l=0,
while for Kq-Free Editing and q≥6, NP-hardness for
l=0 even holds for vertex-disjoint packings of Kq.

[ bib |
DOI |
slides |
http ]
Back

*This file was generated by
bibtex2html 1.98.*