Parameterizing edge modification problems above lower bounds

René Van Bevern, Vincent Froese, Christian Komusiewicz

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

2 Цитирования (Scopus)

Аннотация

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.

Язык оригиналаанглийский
Название основной публикацииComputer Science - Theory and Applications - 11th International Computer Science Symposium in Russia, CSR 2016, Proceedings
РедакторыGerhard J. Woeginger, Alexander S. Kulikov
ИздательSpringer-Verlag GmbH and Co. KG
Страницы57-72
Число страниц16
ISBN (печатное издание)9783319341705
DOI
СостояниеОпубликовано - 1 янв 2016
Событие11th International Computer Science Symposium in Russia, CSR 2016 - St. Petersburg, Российская Федерация
Продолжительность: 9 июн 201613 июн 2016

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том9691
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция11th International Computer Science Symposium in Russia, CSR 2016
СтранаРоссийская Федерация
ГородSt. Petersburg
Период09.06.201613.06.2016

ГРНТИ

  • 27 МАТЕМАТИКА

Fingerprint Подробные сведения о темах исследования «Parameterizing edge modification problems above lower bounds». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Van Bevern, R., Froese, V., & Komusiewicz, C. (2016). Parameterizing edge modification problems above lower bounds. В G. J. Woeginger, & A. S. Kulikov (Ред.), Computer Science - Theory and Applications - 11th International Computer Science Symposium in Russia, CSR 2016, Proceedings (стр. 57-72). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 9691). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-319-34171-2_5