Document Open Access Logo

A Cubic Vertex-Kernel for Trivially Perfect Editing

Authors Maël Dumas, Anthony Perez, Ioan Todinca

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.45.pdf
  • Filesize: 0.74 MB
  • 14 pages

Document Identifiers

Author Details

Maël Dumas
  • Univ. Orléans, INSA Centre Val de Loire, LIFO EA 4022, F-45067 Orléans, France
Anthony Perez
  • Univ. Orléans, INSA Centre Val de Loire, LIFO EA 4022, F-45067 Orléans, France
Ioan Todinca
  • Univ. Orléans, INSA Centre Val de Loire, LIFO EA 4022, F-45067 Orléans, France

Cite AsGet BibTex

Maël Dumas, Anthony Perez, and Ioan Todinca. A Cubic Vertex-Kernel for Trivially Perfect Editing. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.MFCS.2021.45

Abstract

We consider the Trivially Perfect Editing problem, where one is given an undirected graph G = (V,E) and a parameter k ∈ ℕ and seeks to edit (add or delete) at most k edges from G to obtain a trivially perfect graph. The related Trivially Perfect Completion and Trivially Perfect Deletion problems are obtained by only allowing edge additions or edge deletions, respectively. Trivially perfect graphs are both chordal and cographs, and have applications related to the tree-depth width parameter and to social network analysis. All variants of the problem are known to be NP-complete [Burzyn et al., 2006; James Nastos and Yong Gao, 2013] and to admit so-called polynomial kernels [Pål Grønås Drange and Michał Pilipczuk, 2018; Jiong Guo, 2007]. More precisely, the existence of an O(k³) vertex-kernel for Trivially Perfect Completion was announced by Guo [Jiong Guo, 2007] but without a stand-alone proof. More recently, Drange and Pilipczuk [Pål Grønås Drange and Michał Pilipczuk, 2018] provided O(k⁷) vertex-kernels for these problems and left open the existence of cubic vertex-kernels. In this work, we answer positively to this question for all three variants of the problem.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Parameterized complexity
  • kernelization algorithms
  • graph modification
  • trivially perfect graphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. N. R. Aravind, R. B. Sandeep, and Naveen Sivadasan. Dichotomy results on the hardness of h-free edge modification problems. SIAM J. Discret. Math., 31(1):542-561, 2017. URL: https://doi.org/10.1137/16M1055797.
  2. Gabriel Bathie, Nicolas Bousquet, and Théo Pierron. (Sub)linear kernels for edge modification problems towards structured graph classes. In preparation, 2021. Google Scholar
  3. Stéphane Bessy, Christophe Paul, and Anthony Perez. Polynomial kernels for 3-leaf power graph modification problems. Discret. Appl. Math., 158(16):1732-1744, 2010. URL: https://doi.org/10.1016/j.dam.2010.07.002.
  4. Stéphane Bessy and Anthony Perez. Polynomial kernels for proper interval completion and related problems. Inf. Comput., 231:89-108, 2013. URL: https://doi.org/10.1016/j.ic.2013.08.006.
  5. Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, and Michał Pilipczuk. A subexponential parameterized algorithm for proper interval completion. SIAM J. Discret. Math., 29(4):1961-1987, 2015. URL: https://doi.org/10.1137/140988565.
  6. Pablo Burzyn, Flavia Bonomo, and Guillermo Durán. Np-completeness results for edge modification problems. Discrete Applied Mathematics, 154(13):1824-1844, 2006. URL: https://doi.org/10.1016/j.dam.2006.03.031.
  7. 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.
  8. 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.
  9. Yixin Cao and Yuping Ke. Improved kernels for edge modification problems, 2021. URL: http://arxiv.org/abs/2104.14510.
  10. Yixin Cao and Dániel Marx. Chordal editing is fixed-parameter tractable. Algorithmica, 75(1):118-137, 2016. URL: https://doi.org/10.1007/s00453-015-0014-x.
  11. Christophe Crespelle, Pål Grønås Drange, Fedor V. Fomin, and Petr A. Golovach. A survey of parameterized algorithms and the complexity of edge modification. CoRR, abs/2001.06867, 2020. URL: http://arxiv.org/abs/2001.06867.
  12. Pål Grønås Drange, Fedor V. Fomin, Michał Pilipczuk, and Yngve Villanger. Exploring the subexponential complexity of completion problems. ACM Trans. Comput. Theory, 7(4):14:1-14:38, 2015. URL: https://doi.org/10.1145/2799640.
  13. Pål Grønås Drange and Michał Pilipczuk. A polynomial kernel for trivially perfect editing. Algorithmica, 80(12):3481-3524, 2018. URL: https://doi.org/10.1007/s00453-017-0401-6.
  14. Maël Dumas, Anthony Perez, and Ioan Todinca. A cubic vertex-kernel for trivially perfect editing. CoRR, abs/2105.08549, 2021. URL: http://arxiv.org/abs/2105.08549.
  15. Ehab S El-Mallah and Charles J Colbourn. The complexity of some edge deletion problems. IEEE transactions on circuits and systems, 35(3):354-362, 1988. URL: https://doi.org/10.1109/31.1748.
  16. Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. Planar F-deletion: Approximation, kernelization and optimal FPT algorithms. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 470-479. IEEE Computer Society, 2012. URL: https://doi.org/10.1109/FOCS.2012.62.
  17. Fedor V Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Kernelization: theory of parameterized preprocessing. Cambridge University Press, 2019. Google Scholar
  18. Fedor V. Fomin and Yngve Villanger. Subexponential parameterized algorithm for minimum fill-in. SIAM J. Comput., 42(6):2197-2216, 2013. URL: https://doi.org/10.1137/11085390X.
  19. Esha Ghosh, Sudeshna Kolay, Mrinal Kumar, Pranabendu Misra, Fahad Panolan, Ashutosh Rai, and M. S. Ramanujan. Faster parameterized algorithms for deletion to split graphs. Algorithmica, 71(4):989-1006, 2015. URL: https://doi.org/10.1007/s00453-013-9837-5.
  20. Martin Charles Golumbic. Trivially perfect graphs. Discret. Math., 24(1):105-107, 1978. URL: https://doi.org/10.1016/0012-365X(78)90178-4.
  21. Martin Charles Golumbic, Haim Kaplan, and Ron Shamir. On the complexity of DNA physical mapping. Advances in Applied Mathematics, 15(3):251-261, 1994. URL: https://doi.org/10.1006/aama.1994.1009.
  22. Sylvain Guillemot, Frédéric Havet, Christophe Paul, and Anthony Perez. On the (non-)existence of polynomial kernels for P_l-free edge modification problems. Algorithmica, 65(4):900-926, 2013. URL: https://doi.org/10.1007/s00453-012-9619-5.
  23. Jiong Guo. Problem kernels for NP-complete edge deletion problems: Split and related graphs. In Takeshi Tokuyama, editor, Algorithms and Computation, 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17-19, 2007, Proceedings, volume 4835 of Lecture Notes in Computer Science, pages 915-926. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-77120-3_79.
  24. Pavol Hell, Ron Shamir, and Roded Sharan. A fully dynamic algorithm for recognizing and representing proper interval graphs. SIAM J. Comput., 31(1):289-305, 2001. URL: https://doi.org/10.1137/S0097539700372216.
  25. Haim Kaplan, Ron Shamir, and Robert Endre Tarjan. Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs. SIAM J. Comput., 28(5):1906-1922, 1999. URL: https://doi.org/10.1137/S0097539796303044.
  26. Stefan Kratsch and Magnus Wahlström. Two edge modification problems without polynomial kernels. In Jianer Chen and Fedor V. Fomin, editors, Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, September 10-11, 2009, Revised Selected Papers, volume 5917 of Lecture Notes in Computer Science, pages 264-275. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-11269-0_22.
  27. Yunlong Liu, Jianxin Wang, and Jiong Guo. An overview of kernelization algorithms for graph modification problems. Tsinghua Science and Technology, 19(4):346-357, 2014. URL: https://doi.org/10.1109/TST.2014.6867517.
  28. 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, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 72:1-72:25. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ESA.2020.72.
  29. James Nastos and Yong Gao. Familial groups in social networks. Soc. Networks, 35(3):439-450, 2013. URL: https://doi.org/10.1016/j.socnet.2013.05.001.
  30. Jaroslav Nesetril and Patrice Ossona de Mendez. On low tree-depth decompositions. Graphs Comb., 31(6):1941-1963, 2015. URL: https://doi.org/10.1007/s00373-015-1569-7.
  31. Fábio Protti, Maise Dantas da Silva, and Jayme Luiz Szwarcfiter. Applying modular decomposition to parameterized cluster editing problems. Theory Comput. Syst., 44(1):91-104, 2009. URL: https://doi.org/10.1007/s00224-007-9032-7.
  32. Jing-Ho Yan, Jer-Jeong Chen, and Gerard J Chang. Quasi-threshold graphs. Discrete applied mathematics, 69(3):247-255, 1996. Google Scholar
  33. Mihalis Yannakakis. Computing the minimum fill-in is NP-complete. SIAM Journal on Algebraic Discrete Methods, 2(1):77-79, 1981. URL: https://doi.org/10.1137/0602010.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact