Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Parameterizing edge modification problems above lower bounds. / Van Bevern, René; Froese, Vincent; Komusiewicz, Christian.
Computer Science - Theory and Applications - 11th International Computer Science Symposium in Russia, CSR 2016, Proceedings. ed. / Gerhard J. Woeginger; Alexander S. Kulikov. Springer, 2016. p. 57-72 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9691).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
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
T2 - 11th International Computer Science Symposium in Russia, CSR 2016
Y2 - 9 June 2016 through 13 June 2016
ER -
ID: 22339481