dc.contributor.author | Eiben, Eduard | |
dc.contributor.author | Lochet, William | |
dc.contributor.author | Saurabh, Saket | |
dc.date.accessioned | 2021-07-08T09:04:23Z | |
dc.date.available | 2021-07-08T09:04:23Z | |
dc.date.created | 2021-02-07T15:02:34Z | |
dc.date.issued | 2020 | |
dc.identifier.isbn | 978-3-95977-172-6 | |
dc.identifier.issn | 1868-8969 | |
dc.identifier.uri | https://hdl.handle.net/11250/2763887 | |
dc.description.abstract | For a fixed graph H, the H-free Edge Editing problem asks whether we can modify a given graph G by adding or deleting at most k edges such that the resulting graph does not contain H as an induced subgraph. The problem is known to be NP-complete for all fixed H with at least 3 vertices and it admits a 2^O(k)n^O(1) algorithm. Cai and Cai [Algorithmica (2015) 71:731–757] showed that, assuming coNP ⊈ NP/poly, H-free Edge Editing does not admit a polynomial kernel whenever H or its complement is a path or a cycle with at least 4 edges or a 3-connected graph with at least one edge missing. Based on their result, very recently Marx and Sandeep [ESA 2020] conjectured that if H is a graph with at least 5 vertices, then H-free Edge Editing has a polynomial kernel if and only if H is a complete or empty graph, unless coNP ⊆ NP/poly. Furthermore they gave a list of 9 graphs, each with five vertices, such that if H-free Edge Editing for these graphs does not admit a polynomial kernel, then the conjecture is true. Therefore, resolving the kernelization of H-free Edge Editing for graphs H with 4 and 5 vertices plays a crucial role in obtaining a complete dichotomy for this problem. In this paper, we positively answer the question of compressibility for one of the last two unresolved graphs H on 4 vertices. Namely, we give the first polynomial kernel for Paw-free Edge Editing with O(k⁶) vertices. | en_US |
dc.language.iso | eng | en_US |
dc.publisher | Schloss Dagstuhl – Leibniz Center for Informatics | en_US |
dc.rights | Navngivelse 4.0 Internasjonal | * |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/deed.no | * |
dc.title | A Polynomial Kernel for Paw-Free Editing | en_US |
dc.type | Journal article | en_US |
dc.type | Peer reviewed | en_US |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright the authors | en_US |
cristin.ispublished | true | |
cristin.fulltext | original | |
cristin.qualitycode | 1 | |
dc.identifier.doi | 10.4230/LIPIcs.IPEC.2020.10 | |
dc.identifier.cristin | 1887423 | |
dc.source.journal | Leibniz International Proceedings in Informatics | en_US |
dc.source.pagenumber | 10:1-10:15 | en_US |
dc.identifier.citation | Leibniz International Proceedings in Informatics. 2020, 180, 10. | en_US |
dc.source.volume | 180 | en_US |