Document Open Access Logo

Polynomial Kernels for Strictly Chordal Edge Modification Problems

Authors Maël Dumas, Anthony Perez, Ioan Todinca

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2021.17.pdf
  • Filesize: 0.8 MB
  • 16 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 As Get BibTex

Maël Dumas, Anthony Perez, and Ioan Todinca. Polynomial Kernels for Strictly Chordal Edge Modification Problems. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.IPEC.2021.17

Abstract

We consider the Strictly Chordal 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 strictly chordal graph. Problems Strictly Chordal Completion and Strictly Chordal Deletion are defined similarly, by only allowing edge additions for the former, and only edge deletions for the latter. Strictly chordal graphs are a generalization of 3-leaf power graphs and a subclass of 4-leaf power graphs. They can be defined, e.g., as dart and gem-free chordal graphs. We prove the NP-completeness for all three variants of the problem and provide an O(k³) vertex-kernel for the completion version and O(k⁴) vertex-kernels for the two others.

Subject Classification

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

Metrics

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

References

  1. Hans-Jürgen Bandelt and Henry Martyn Mulder. Distance-hereditary graphs. J. Comb. Theory, Ser. B, 41(2):182-208, 1986. URL: https://doi.org/10.1016/0095-8956(86)90043-2.
  2. Gabriel Bathie, Nicolas Bousquet, and Théo Pierron. (sub)linear kernels for edge modification problems towards structured graph classes. CoRR, abs/2105.09566, 2021. URL: http://arxiv.org/abs/2105.09566.
  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. Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Danny Hermelin. On problems without polynomial kernels. J. Comput. Syst. Sci., 75(8):423-434, 2009. URL: https://doi.org/10.1016/j.jcss.2009.04.001.
  6. Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Kernelization lower bounds by cross-composition. SIAM J. Discret. Math., 28(1):277-305, 2014. URL: https://doi.org/10.1137/120880240.
  7. Hans L. Bodlaender, Stéphan Thomassé, and Anders Yeo. Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci., 412(35):4570-4578, 2011. URL: https://doi.org/10.1016/j.tcs.2011.04.039.
  8. 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.
  9. 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.
  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. Christophe Crespelle, Benjamin Gras, and Anthony Perez. Completion to chordal distance-hereditary graphs: a quartic vertex-kernel. Accepted for publication at International Workshop on Graph-Theoretic Concepts in Computer Science, 2021. Google Scholar
  13. Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms, volume 5. Springer, 2015. Google Scholar
  14. Michael Dom, Jiong Guo, Falk Hüffner, and Rolf Niedermeier. Error compensation in leaf power problems. Algorithmica, 44(4):363-381, 2006. URL: https://doi.org/10.1007/s00453-005-1180-z.
  15. Michael Dom, Jiong Guo, Falk Hüffner, and Rolf Niedermeier. Closest 4-leaf power is fixed-parameter tractable. Discret. Appl. Math., 156(18):3345-3361, 2008. URL: https://doi.org/10.1016/j.dam.2008.01.007.
  16. 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.
  17. 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.
  18. Martin Charles Golumbic and Uri N. Peled. Block duplicate graphs and a hierarchy of chordal graphs. Discret. Appl. Math., 124(1-3):67-71, 2002. URL: https://doi.org/10.1016/S0166-218X(01)00330-4.
  19. 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.
  20. 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.
  21. 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.
  22. William Kennedy. Strictly chordal graphs and phylogenetic roots. Master’s thesis, University of Alberta, 2005. Google Scholar
  23. William Kennedy, Guohui Lin, and Guiying Yan. Strictly chordal graphs are leaf powers. Journal of Discrete Algorithms, 4(4):511-525, 2006. URL: https://doi.org/10.1016/j.jda.2005.06.005.
  24. Stefan Kratsch and Magnus Wahlström. Two edge modification problems without polynomial kernels. Discret. Optim., 10(3):193-199, 2013. URL: https://doi.org/10.1016/j.disopt.2013.02.001.
  25. Mirko Křivánek and Jaroslav Morávek. Np-hard problems in hierarchical-tree clustering. Acta Informatica, 23(3):311-323, 1986. URL: https://doi.org/10.1007/BF00289116.
  26. Lilian Markenzon and Christina Fraga Esteves Maciel Waga. New results on ptolemaic graphs. Discret. Appl. Math., 196:135-140, 2015. URL: https://doi.org/10.1016/j.dam.2014.03.024.
  27. Assaf Natanzon. Complexity and approximation of some graph modification problems. University of Tel-Aviv, 1999. Google Scholar
  28. Naomi Nishimura, Prabhakar Ragde, and Dimitrios M. Thilikos. On graph powers for leaf-labeled trees. J. Algorithms, 42(1):69-108, 2002. URL: https://doi.org/10.1006/jagm.2001.1195.
  29. 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.
  30. Ron Shamir, Roded Sharan, and Dekel Tsur. Cluster graph modification problems. Discret. Appl. Math., 144(1-2):173-182, 2004. URL: https://doi.org/10.1016/j.dam.2004.01.007.
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 About DROPS Imprint Privacy Contact