@article{BFK18,
  title =	 {Parameterizing edge modification problems above
                  lower bounds},
  author =	 {René van Bevern and Vincent Froese and Christian
                  Komusiewicz},
  url_Preprint = {http://arxiv.org/abs/1512.04047},
  doi =		 {10.1007/s00224-016-9746-5},
  url_Slides =	 {http://rvb.su/pdf/above-guarantee-editing-csr16.pdf},
  year =	 2018,
  date =	 {2018-04-01},
  journal =	 {Theory of Computing Systems},
  abstract =	 {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 develop a framework
                  of generic data reduction rules to 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 solution size.  For K_3-Free
                  Editing, we also prove NP-hardness in case of
                  edge-disjoint packings of K_3s and l=0, while for
                  K_q-Free Editing and qge 6, NP-hardness for l=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.},
  keywords =	 {algorithmic graph theory, graph modification,
                  invited, network analysis, NP-hard, parameterized
                  complexity},
  volume =	 "62",
  number =	 "3",
  pages =	 "739--770",
}

{"_id":"WS2JPZBWbK3cBTbep","bibbaseid":"vanbevern-froese-komusiewicz-parameterizingedgemodificationproblemsabovelowerbounds-2018","authorIDs":["2fwXJtKDCNhaSNr5s"],"author_short":["van Bevern, R.","Froese, V.","Komusiewicz, C."],"bibdata":{"bibtype":"article","type":"article","title":"Parameterizing edge modification problems above lower bounds","author":[{"firstnames":["René"],"propositions":["van"],"lastnames":["Bevern"],"suffixes":[]},{"firstnames":["Vincent"],"propositions":[],"lastnames":["Froese"],"suffixes":[]},{"firstnames":["Christian"],"propositions":[],"lastnames":["Komusiewicz"],"suffixes":[]}],"url_preprint":"http://arxiv.org/abs/1512.04047","doi":"10.1007/s00224-016-9746-5","url_slides":"http://rvb.su/pdf/above-guarantee-editing-csr16.pdf","year":"2018","date":"2018-04-01","journal":"Theory of Computing Systems","abstract":"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 develop a framework of generic data reduction rules to 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 solution size. For K_3-Free Editing, we also prove NP-hardness in case of edge-disjoint packings of K_3s and l=0, while for K_q-Free Editing and qge 6, NP-hardness for l=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.","keywords":"algorithmic graph theory, graph modification, invited, network analysis, NP-hard, parameterized complexity","volume":"62","number":"3","pages":"739–770","bibtex":"@article{BFK18,\n title =\t {Parameterizing edge modification problems above\n lower bounds},\n author =\t {René van Bevern and Vincent Froese and Christian\n Komusiewicz},\n url_Preprint = {http://arxiv.org/abs/1512.04047},\n doi =\t\t {10.1007/s00224-016-9746-5},\n url_Slides =\t {http://rvb.su/pdf/above-guarantee-editing-csr16.pdf},\n year =\t 2018,\n date =\t {2018-04-01},\n journal =\t {Theory of Computing Systems},\n abstract =\t {We study the parameterized complexity of a variant\n of the F-free Editing problem: Given a graph G and a\n natural number k, is it possible to modify at most k\n edges in G so that the resulting graph contains no\n induced subgraph isomorphic to F? In our variant,\n the input additionally contains a vertex-disjoint\n packing H of induced subgraphs of G, which provides\n a lower bound h(H) on the number of edge\n modifications required to transform G into an F-free\n graph. While earlier works used the number k as\n parameter or structural parameters of the input\n graph G, we consider instead the parameter\n l:=k-h(H), that is, the number of edge modifications\n above the lower bound h(H). We develop a framework\n of generic data reduction rules to show\n fixed-parameter tractability with respect to l for\n K_3-Free Editing, Feedback Arc Set in Tournaments,\n and Cluster Editing when the packing H contains\n subgraphs with bounded solution size. For K_3-Free\n Editing, we also prove NP-hardness in case of\n edge-disjoint packings of K_3s and l=0, while for\n K_q-Free Editing and qge 6, NP-hardness for l=0 even\n holds for vertex-disjoint packings of K_qs. In\n addition, we provide NP-hardness results for F-free\n Vertex Deletion, were the aim is to delete a minimum\n number of vertices to make the input graph F-free.},\n keywords =\t {algorithmic graph theory, graph modification,\n invited, network analysis, NP-hard, parameterized\n complexity},\n volume =\t \"62\",\n number =\t \"3\",\n pages =\t \"739--770\",\n}\n\n","author_short":["van Bevern, R.","Froese, V.","Komusiewicz, C."],"key":"BFK18","id":"BFK18","bibbaseid":"vanbevern-froese-komusiewicz-parameterizingedgemodificationproblemsabovelowerbounds-2018","role":"author","urls":{" preprint":"http://arxiv.org/abs/1512.04047"," slides":"http://rvb.su/pdf/above-guarantee-editing-csr16.pdf"},"keyword":["algorithmic graph theory","graph modification","invited","network analysis","NP-hard","parameterized complexity"],"metadata":{"authorlinks":{"van bevern, r":"https://rvb.su/"}},"downloads":3,"html":""},"bibtype":"article","biburl":"http://rvb.su/rvb.bib","creationDate":"2021-01-06T14:16:51.470Z","downloads":3,"keywords":["algorithmic graph theory","graph modification","invited","network analysis","np-hard","parameterized complexity"],"search_terms":["parameterizing","edge","modification","problems","above","lower","bounds","van bevern","froese","komusiewicz"],"title":"Parameterizing edge modification problems above lower bounds","year":2018,"dataSources":["SMwzc9Bzq5Np5ikev","G5GefJqqu2DtnCZXz"]}