LIPIcs.IPEC.2020.10.pdf
- Filesize: 0.64 MB
- 15 pages
Document
A Polynomial Kernel for Paw-Free Editing
Authors
Eduard Eiben 
,
-
Part of:
Volume:
15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Parameterized and Exact Computation (IPEC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-12-04
File
Document Identifiers
Author Details
Acknowledgements
The authors wish to thank the anonymous referees for helping in the presentation of the paper and pointing out some missing argument in Section 5.
Cite AsGet BibTex
Eduard Eiben, William Lochet, and Saket Saurabh. A Polynomial Kernel for Paw-Free Editing. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.IPEC.2020.10
https://doi.org/10.4230/LIPIcs.IPEC.2020.10
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Design and analysis of algorithms
- Theory of computation → Graph algorithms analysis
- Theory of computation → Parameterized complexity and exact algorithms
Keywords
- Kernelization
- Paw-free graph
- H-free editing
- graph modification problem
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- N. R. Aravind, R. B. Sandeep, and Naveen Sivadasan. Dichotomy results on the hardness of H-free edge modification problems. SIAM J. Discrete Math., 31(1):542-561, 2017. URL: https://doi.org/10.1137/16M1055797.
-
Hans L Bodlaender, Leizhen Cai, Jianer Chen, Michael R Fellows, Jan Arne Telle, and Dániel Marx. Open problems in parameterized and exact computation-iwpec 2006. UU-CS, 2006, 2006.
- Leizhen Cai. Fixed-parameter tractability of graph modification problems for hereditary properties. Inf. Process. Lett., 58(4):171-176, 1996. URL: https://doi.org/10.1016/0020-0190(96)00050-6.
- Leizhen Cai and Yufei Cai. Incompressibility of H-free edge modification problems. Algorithmica, 71(3):731-757, 2015. URL: https://doi.org/10.1007/s00453-014-9937-x.
-
Yufei Cai. Polynomial kernelisation of H-free edge modification problems. Mphil thesis, Department of Computer Science and Engineering, The Chinese University of Hong Kong, Hong Kong SAR, China, 2012.
- Yixin Cao, Yuping Ke, and Hanchun Yuan. Polynomial kernels for paw-free edge modification problems. CoRR, abs/2003.11273, 2020. URL: http://arxiv.org/abs/2003.11273.
- Yixin Cao, Ashutosh Rai, R. B. Sandeep, and Junjie Ye. A polynomial kernel for diamond-free editing. In 26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland, pages 10:1-10:13, 2018. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.10.
- Maria Chudnovsky and Paul D. Seymour. Claw-free graphs. IV. decomposition theorem. J. Comb. Theory, Ser. B, 98(5):839-938, 2008. URL: https://doi.org/10.1016/j.jctb.2007.06.007.
-
Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015.
-
R. Diestel. Graph Theory, 4th Edition. Springer, 2012.
-
Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013.
- Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006. URL: https://doi.org/10.1007/3-540-29953-X.
- Sylvain Guillemot, Frédéric Havet, Christophe Paul, and Anthony Perez. On the (non-)existence of polynomial kernels for P_𝓁-free edge modification problems. Algorithmica, 65(4):900-926, 2013. URL: https://doi.org/10.1007/s00453-012-9619-5.
- Stefan Kratsch and Magnus Wahlström. Two edge modification problems without polynomial kernels. Discrete Optimization, 10(3):193-199, 2013. URL: https://doi.org/10.1016/j.disopt.2013.02.001.
- John M. Lewis and Mihalis Yannakakis. The node-deletion problem for hereditary properties is NP-complete. J. Comput. Syst. Sci., 20(2):219-230, 1980. URL: https://doi.org/10.1016/0022-0000(80)90060-4.
- Dániel Marx and R. B. Sandeep. Incompressibility of H-Free Edge Modification Problems: Towards a Dichotomy. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms (ESA 2020), volume 173 of Leibniz International Proceedings in Informatics (LIPIcs), pages 72:1-72:25, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ESA.2020.72.
- Stephan Olariu. Paw-free graphs. Information Processing Letters, 28(1):53-54, 1988. URL: https://doi.org/10.1016/0020-0190(88)90143-3.
- R. B. Sandeep and Naveen Sivadasan. Parameterized lower bound and improved kernel for diamond-free edge deletion. In 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, September 16-18, 2015, Patras, Greece, pages 365-376, 2015. URL: https://doi.org/10.4230/LIPIcs.IPEC.2015.365.