2026-07-23T07:16:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15384 2024-03-06T10:55:37Z ddc:004 open_access

A Polynomial Kernel for Deletion to Ptolemaic Graphs Agrawal, Akanksha Anand, Aditya Saurabh, Saket Ptolemaic Deletion Kernelization Parameterized Complexity Gem-free chordal graphs 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Akanksha Agrawal and Aditya Anand and Saket Saurabh 2021 Is Part Of LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2021.1 urn:nbn:de:0030-drops-153840 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.1 eng https://creativecommons.org/licenses/by/4.0/legalcode