SCIENCE@home

Parameterizing Edge Modification Problems Above Lower Bounds

René van Bevern,Vincent Froese,Christian Komusiewicz

Published 2015 in Theory of Computing Systems

ABSTRACT

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 ℋ$\mathcal {H}$ of induced subgraphs of G, which provides a lower bound h(ℋ)$h(\mathcal {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 ℓ:=k−h(ℋ)$\ell :=k-h(\mathcal {H})$, that is, the number of edge modifications above the lower bound h(ℋ)$h(\mathcal {H})$. We develop a framework of generic data reduction rules to show fixed-parameter tractability with respect to ℓ for K3-Free Editing, Feedback Arc Set in Tournaments, and Cluster Editing when the packing ℋ$\mathcal {H}$ contains subgraphs with bounded solution size. For K3-Free Editing, we also prove NP-hardness in case of edge-disjoint packings of K3s and ℓ = 0, while for Kq-Free Editing and q ≥ 6, NP-hardness for ℓ = 0 even holds for vertex-disjoint packings of Kqs. 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.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-50 of 50 references · Page 1 of 1

CITED BY

Showing 1-17 of 17 citing papers · Page 1 of 1