TY - JOUR

T1 - Parameterizing Edge Modification Problems Above Lower Bounds

AU - van Bevern, René

AU - Froese, Vincent

AU - Komusiewicz, Christian

N1 - Publisher Copyright: © 2017, Springer Science+Business Media New York.

PY - 2018/4/1

Y1 - 2018/4/1

N2 - 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 ℋ of induced subgraphs of G, which provides a lower bound 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(ℋ) , that is, the number of edge modifications above the lower bound h(ℋ). We develop a framework of generic data reduction rules to show fixed-parameter tractability with respect to ℓ for K 3-Free Editing, Feedback Arc Set in Tournaments, and Cluster Editing when the packing ℋ 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 ℓ = 0, while for K q-Free Editing and q ≥ 6, NP-hardness for ℓ = 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.

AB - 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 ℋ of induced subgraphs of G, which provides a lower bound 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(ℋ) , that is, the number of edge modifications above the lower bound h(ℋ). We develop a framework of generic data reduction rules to show fixed-parameter tractability with respect to ℓ for K 3-Free Editing, Feedback Arc Set in Tournaments, and Cluster Editing when the packing ℋ 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 ℓ = 0, while for K q-Free Editing and q ≥ 6, NP-hardness for ℓ = 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.

KW - Cluster editing

KW - Feedback arc set

KW - Fixed-parameter algorithm

KW - Graph-based Clustering

KW - Kernelization

KW - NP-hard problem

KW - Subgraph packing

KW - FEEDBACK SET PROBLEMS

KW - ALGORITHMS

KW - TRACTABILITY

KW - KERNELS

UR - http://www.scopus.com/inward/record.url?scp=85009785269&partnerID=8YFLogxK

U2 - 10.1007/s00224-016-9746-5

DO - 10.1007/s00224-016-9746-5

M3 - Article

AN - SCOPUS:85009785269

VL - 62

SP - 739

EP - 770

JO - Theory of Computing Systems

JF - Theory of Computing Systems

SN - 1432-4350

IS - 3

ER -