Polynomial Kernels for Paw-Free Edge Modification Problems

Yixin Cao, Yuping Ke, Hanchun Yuan

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

Abstract

Let H be a fixed graph. Given a graph G and an integer k, the H-free edge modification problem asks whether it is possible to modify at most k edges in G to make it H-free. Sandeep and Sivadasan (IPEC 2015) asks whether the paw-free completion problem and the paw-free edge deletion problem admit polynomial kernels. We answer both questions affirmatively by presenting, respectively, O(k)-vertex and -vertex kernels for them. This is part of an ongoing program that aims at understanding compressibility of H-free edge modification problems.

Original languageEnglish
Title of host publicationTheory and Applications of Models of Computation - 16th International Conference, TAMC 2020, Proceedings
EditorsJianer Chen, Qilong Feng, Jinhui Xu
PublisherSpringer Science and Business Media Deutschland GmbH
Pages37-49
Number of pages13
ISBN (Print)9783030592660
DOIs
Publication statusPublished - 2020
Event16th Annual Conference on Theory and Applications of Models of Computation, TAMC 2020 - Changsha, China
Duration: 18 Oct 202020 Oct 2020

Publication series

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

Conference

Conference16th Annual Conference on Theory and Applications of Models of Computation, TAMC 2020
Country/TerritoryChina
CityChangsha
Period18/10/2020/10/20

Keywords

  • Graph modification
  • Kernelization
  • Paw-free graph

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this