License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2021.1
URN: urn:nbn:de:0030-drops-153840
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15384/
Go to the corresponding LIPIcs Volume Portal

Agrawal, Akanksha ; Anand, Aditya ; Saurabh, Saket

A Polynomial Kernel for Deletion to Ptolemaic Graphs

pdf-format:
LIPIcs-IPEC-2021-1.pdf (0.8 MB)

Abstract

For a family of graphs F, given a graph G and an integer k, the F-Deletion problem asks whether we can delete at most k vertices from G to obtain a graph in the family F. The F-Deletion problems for all non-trivial families F that satisfy the hereditary property on induced subgraphs are known to be NP-hard by a result of Yannakakis (STOC'78). Ptolemaic graphs are the graphs that satisfy the Ptolemy inequality, and they are the intersection of chordal graphs and distance-hereditary graphs. Equivalently, they form the set of graphs that do not contain any chordless cycles or a gem as an induced subgraph. (A gem is the graph on 5 vertices, where four vertices form an induced path, and the fifth vertex is adjacent to all the vertices of this induced path.) The Ptolemaic Deletion problem is the F-Deletion problem, where F is the family of Ptolemaic graphs. In this paper we study Ptolemaic Deletion from the viewpoint of Kernelization Complexity, and obtain a kernel with ?(k⁶) vertices for the problem.

BibTeX - Entry

@InProceedings{agrawal_et_al:LIPIcs.IPEC.2021.1,
  author =	{Agrawal, Akanksha and Anand, Aditya and Saurabh, Saket},
  title =	{{A Polynomial Kernel for Deletion to Ptolemaic Graphs}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{1:1--1:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15384},
  URN =		{urn:nbn:de:0030-drops-153840},
  doi =		{10.4230/LIPIcs.IPEC.2021.1},
  annote =	{Keywords: Ptolemaic Deletion, Kernelization, Parameterized Complexity, Gem-free chordal graphs}
}

Keywords: Ptolemaic Deletion, Kernelization, Parameterized Complexity, Gem-free chordal graphs
Collection: 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)
Issue Date: 2021
Date of publication: 22.11.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI