Parameterizing edge modification problems above lower bounds. van Bevern, R., Froese, V., & Komusiewicz, C. In Kulikov, A. S. & Woeginger, G. J., editors, CSR 2016, volume 9691, of Lecture Notes in Computer Science, pages 57-72. Springer, 2016.
![Parameterizing edge modification problems above lower bounds [pdf]](https://bibbase.org/img/filetypes/pdf.svg "pdf")
Slides doi abstract bibtex
Slides doi abstract bibtex 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 the parameter l:=k-h(H) instead, that is, the number of edge modifications above the lower bound h(H). We show fixed-parameter tractability with respect to l for K_3-Free Editing, Feedback Arc Set in Tournaments, and Cluster Editing when the packing H contains subgraphs with bounded modification cost. 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 Kq.
@incollection{BFK16,
title = {Parameterizing edge modification problems above
lower bounds},
doi = {10.1007/978-3-319-34171-2_5},
author = {René van Bevern and Vincent Froese and Christian
Komusiewicz},
url_Slides = {http://rvb.su/pdf/above-guarantee-editing-csr16.pdf},
isbn = {978-3-319-34170-5},
year = {2016},
date = {2016-05-31},
booktitle = {CSR 2016},
editor = {Alexander S. Kulikov and Gerhard J. Woeginger},
volume = {9691},
pages = {57-72},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
abstract = {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 the
parameter l:=k-h(H) instead, that is, the number of
edge modifications above the lower bound h(H). We
show fixed-parameter tractability with respect to l
for K_3-Free Editing, Feedback Arc Set in
Tournaments, and Cluster Editing when the packing H
contains subgraphs with bounded modification
cost. 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 Kq.},
keywords = {graph modification, parameterized complexity},
}Downloads: 0
{"_id":"NphJAzp5nRhJr9pn7","bibbaseid":"vanbevern-froese-komusiewicz-parameterizingedgemodificationproblemsabovelowerbounds-2016","downloads":0,"creationDate":"2016-03-07T11:48:39.114Z","title":"Parameterizing edge modification problems above lower bounds","author_short":["van Bevern, R.","Froese, V.","Komusiewicz, C."],"year":2016,"bibtype":"incollection","biburl":"http://rvb.su/rvb.bib","bibdata":{"bibtype":"incollection","type":"incollection","title":"Parameterizing edge modification problems above lower bounds","doi":"10.1007/978-3-319-34171-2_5","author":[{"firstnames":["René"],"propositions":["van"],"lastnames":["Bevern"],"suffixes":[]},{"firstnames":["Vincent"],"propositions":[],"lastnames":["Froese"],"suffixes":[]},{"firstnames":["Christian"],"propositions":[],"lastnames":["Komusiewicz"],"suffixes":[]}],"url_slides":"http://rvb.su/pdf/above-guarantee-editing-csr16.pdf","isbn":"978-3-319-34170-5","year":"2016","date":"2016-05-31","booktitle":"CSR 2016","editor":[{"firstnames":["Alexander","S."],"propositions":[],"lastnames":["Kulikov"],"suffixes":[]},{"firstnames":["Gerhard","J."],"propositions":[],"lastnames":["Woeginger"],"suffixes":[]}],"volume":"9691","pages":"57-72","publisher":"Springer","series":"Lecture Notes in Computer Science","abstract":"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 the parameter l:=k-h(H) instead, that is, the number of edge modifications above the lower bound h(H). We show fixed-parameter tractability with respect to l for K_3-Free Editing, Feedback Arc Set in Tournaments, and Cluster Editing when the packing H contains subgraphs with bounded modification cost. 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 Kq.","keywords":"graph modification, parameterized complexity","bibtex":"@incollection{BFK16,\n title =\t {Parameterizing edge modification problems above\n lower bounds},\n doi =\t\t {10.1007/978-3-319-34171-2_5},\n author =\t {René van Bevern and Vincent Froese and Christian\n Komusiewicz},\n url_Slides =\t {http://rvb.su/pdf/above-guarantee-editing-csr16.pdf},\n isbn =\t {978-3-319-34170-5},\n year =\t {2016},\n date =\t {2016-05-31},\n booktitle =\t {CSR 2016},\n editor =\t {Alexander S. Kulikov and Gerhard J. Woeginger},\n volume =\t {9691},\n pages =\t {57-72},\n publisher =\t {Springer},\n series =\t {Lecture Notes in Computer Science},\n abstract =\t {For a fixed graph F, we study the parameterized\n complexity of a variant of the F-Free Editing\n problem: Given a graph G and a natural number k, is\n it possible to modify at most k edges in G so that\n the resulting graph contains no induced subgraph\n isomorphic to F? In our variant, the input\n additionally contains a vertex-disjoint packing H of\n induced subgraphs of G, which provides a lower bound\n h(H) on the number of edge modifications required to\n transform G into an F-free graph. While earlier\n works used the number k as parameter or structural\n parameters of the input graph G, we consider the\n parameter l:=k-h(H) instead, that is, the number of\n edge modifications above the lower bound h(H). We\n show fixed-parameter tractability with respect to l\n for K_3-Free Editing, Feedback Arc Set in\n Tournaments, and Cluster Editing when the packing H\n contains subgraphs with bounded modification\n cost. For K3-Free Editing, we also prove NP-hardness\n in case of edge-disjoint packings of K3s and l=0,\n while for Kq-Free Editing and q≥6, NP-hardness for\n l=0 even holds for vertex-disjoint packings of Kq.},\n keywords =\t {graph modification, parameterized complexity},\n}\n\n","author_short":["van Bevern, R.","Froese, V.","Komusiewicz, C."],"editor_short":["Kulikov, A. S.","Woeginger, G. J."],"key":"BFK16","id":"BFK16","bibbaseid":"vanbevern-froese-komusiewicz-parameterizingedgemodificationproblemsabovelowerbounds-2016","role":"author","urls":{" slides":"http://rvb.su/pdf/above-guarantee-editing-csr16.pdf"},"keyword":["graph modification","parameterized complexity"],"metadata":{"authorlinks":{"van bevern, r":"https://rvb.su/"}},"downloads":0,"html":""},"search_terms":["parameterizing","edge","modification","problems","above","lower","bounds","van bevern","froese","komusiewicz"],"keywords":["graph modification","parameterized complexity"],"authorIDs":["2fwXJtKDCNhaSNr5s"],"dataSources":["SMwzc9Bzq5Np5ikev","G5GefJqqu2DtnCZXz"]}