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.