TY - GEN

T1 - Parameterizing edge modification problems above lower bounds

AU - Van Bevern, René

AU - Froese, Vincent

AU - Komusiewicz, Christian

PY - 2016/1/1

Y1 - 2016/1/1

N2 - 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 instead the parameter l:= k - h(H), that is, the number of edge modifications above the lower bound h(H). We show fixed-parameter tractability with respect to l for K3-Free Editing, Feedback Arc Set in Tournaments, and Cluster Editing when the packing 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 l = 0, while for Kq-Free Editing and q ≥ 6, NP-hardness for l = 0 even holds for vertex-disjoint packings of Kqs.

AB - 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 instead the parameter l:= k - h(H), that is, the number of edge modifications above the lower bound h(H). We show fixed-parameter tractability with respect to l for K3-Free Editing, Feedback Arc Set in Tournaments, and Cluster Editing when the packing 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 l = 0, while for Kq-Free Editing and q ≥ 6, NP-hardness for l = 0 even holds for vertex-disjoint packings of Kqs.

KW - Cluster editing

KW - Feedback arc set

KW - Fixed-parameter algorithm

KW - Graph-based clustering

KW - Kernelization

KW - NP-hard problem

KW - Subgraph packing

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

U2 - 10.1007/978-3-319-34171-2_5

DO - 10.1007/978-3-319-34171-2_5

M3 - Conference contribution

AN - SCOPUS:84977595293

SN - 9783319341705

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 57

EP - 72

BT - Computer Science - Theory and Applications - 11th International Computer Science Symposium in Russia, CSR 2016, Proceedings

A2 - Woeginger, Gerhard J.

A2 - Kulikov, Alexander S.

PB - Springer-Verlag GmbH and Co. KG

T2 - 11th International Computer Science Symposium in Russia, CSR 2016

Y2 - 9 June 2016 through 13 June 2016

ER -