Research output: Contribution to journal › Article › peer-review
Parameterizing Edge Modification Problems Above Lower Bounds. / van Bevern, René; Froese, Vincent; Komusiewicz, Christian.
In: Theory of Computing Systems, Vol. 62, No. 3, 01.04.2018, p. 739-770.Research output: Contribution to journal › Article › peer-review
}
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 -
ID: 9088129