Parameterizing edge modification problems above lower bounds

René Van Bevern, Vincent Froese, Christian Komusiewicz

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

2 Citations (Scopus)

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 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.

Original languageEnglish
Title of host publicationComputer Science - Theory and Applications - 11th International Computer Science Symposium in Russia, CSR 2016, Proceedings
EditorsGerhard J. Woeginger, Alexander S. Kulikov
PublisherSpringer-Verlag GmbH and Co. KG
Pages57-72
Number of pages16
ISBN (Print)9783319341705
DOIs
Publication statusPublished - 1 Jan 2016
Event11th International Computer Science Symposium in Russia, CSR 2016 - St. Petersburg, Russian Federation
Duration: 9 Jun 201613 Jun 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9691
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference11th International Computer Science Symposium in Russia, CSR 2016
CountryRussian Federation
CitySt. Petersburg
Period09.06.201613.06.2016

Keywords

  • Cluster editing
  • Feedback arc set
  • Fixed-parameter algorithm
  • Graph-based clustering
  • Kernelization
  • NP-hard problem
  • Subgraph packing

State classification of scientific and technological information

  • 27 MATHEMATICS

Fingerprint Dive into the research topics of 'Parameterizing edge modification problems above lower bounds'. Together they form a unique fingerprint.

Cite this