Document Open Access Logo

Improved Kernels for Edge Modification Problems

Authors Yixin Cao , Yuping Ke

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2021.13.pdf
  • Filesize: 0.72 MB
  • 14 pages

Document Identifiers

Author Details

Yixin Cao
  • Department of Computing, Hong Kong Polytechnic University, Hong Kong, China
Yuping Ke
  • Department of Computing, Hong Kong Polytechnic University, Hong Kong, China

Funding

Supported by RGC grants 15201317 and 15226116, and NSFC grant 61972330.

Cite As Get BibTex

Yixin Cao and Yuping Ke. Improved Kernels for Edge Modification Problems. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.IPEC.2021.13

Abstract

In an edge modification problem, we are asked to modify at most k edges of a given graph to make the graph satisfy a certain property. Depending on the operations allowed, we have the completion problems and the edge deletion problems. A great amount of efforts have been devoted to understanding the kernelization complexity of these problems. We revisit several well-studied edge modification problems, and develop improved kernels for them:  
- a 2 k-vertex kernel for the cluster edge deletion problem, 
- a 3 k²-vertex kernel for the trivially perfect completion problem, 
- a 5 k^{1.5}-vertex kernel for the split completion problem and the split edge deletion problem, and 
- a 5 k^{1.5}-vertex kernel for the pseudo-split completion problem and the pseudo-split edge deletion problem.  Moreover, our kernels for split completion and pseudo-split completion have only O(k^{2.5}) edges. Our results also include a 2 k-vertex kernel for the strong triadic closure problem, which is related to cluster edge deletion.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • Kernelization
  • edge modification
  • cluster
  • trivially perfect graphs
  • split graphs

Metrics

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

Related Versions

References

  1. Jonathan F. Buss and Judy Goldsmith. Nondeterminism within P. SIAM Journal on Computing, 22(3):560-572, 1993. URL: https://doi.org/10.1137/0222038.
  2. Leizhen Cai. Fixed-parameter tractability of graph modification problems for hereditary properties. Information Processing Letters, 58(4):171-176, 1996. URL: https://doi.org/10.1016/0020-0190(96)00050-6.
  3. Yixin Cao and Jianer Chen. Cluster editing: Kernelization based on edge cuts. Algorithmica, 64(1):152-169, 2012. URL: https://doi.org/10.1007/s00453-011-9595-1.
  4. 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. arXiv:2001.06867, 2020. Google Scholar
  5. Pål Grønås Drange, Markus Sortland Dregi, Daniel Lokshtanov, and Blair D. Sullivan. On the threshold of intractability. In Nikhil Bansal and Irene Finocchi, editors, Proceedings of the 23rd, volume 9294 of LNCS, pages 411-423. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-48350-3_35.
  6. Pål Grønås Drange, Fedor V. Fomin, Michał Pilipczuk, and Yngve Villanger. Exploring the subexponential complexity of completion problems. ACM Transactions on Computation Theory (TOCT), 7(4):1-38, 2015. URL: https://doi.org/10.1145/2799640.
  7. Pål Grønås Drange and Michal Pilipczuk. A polynomial kernel for trivially perfect editing. Algorithmica, 80(12):3481-3524, 2018. URL: https://doi.org/10.1007/s00453-017-0401-6.
  8. 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), volume 202 of Leibniz International Proceedings in Informatics (LIPIcs), pages 45:1-45:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.MFCS.2021.45.
  9. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Springer, 2006. Google Scholar
  10. 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.
  11. Niels Grüttemeier and Christian Komusiewicz. On the relation of strong triadic closure and cluster deletion. Algorithmica, 82(4):853-880, 2020. URL: https://doi.org/10.1007/s00453-019-00617-1.
  12. Jiong Guo. Problem kernels for NP-complete edge deletion problems: Split and related graphs. In Takeshi Tokuyama, editor, Proceedings of the 18th, volume 4835 of LNCS, pages 915-926. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-77120-3_79.
  13. Peter L. Hammer and Bruno Simeone. The splittance of a graph. Combinatorica, 1(3):275-284, 1981. URL: https://doi.org/10.1007/BF02579333.
  14. Athanasios L. Konstantinidis, Stavros D. Nikolopoulos, and Charis Papadopoulos. Strong triadic closure in cographs and graphs of low maximum degree. Theoretical Computer Science, 740:76-84, 2018. URL: https://doi.org/10.1016/j.tcs.2018.05.012.
  15. Federico Mancini. Graph Modification Problems Related to Graph Classes. PhD thesis, University of Bergen, Bergen, Norway, 2008. Google Scholar
  16. 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, Proceedings of the 28th, 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.
  17. Assaf Natanzon, Ron Shamir, and Roded Sharan. Complexity classification of some edge modification problems. Discrete Applied Mathematics, 113(1):109-128, 2001. URL: https://doi.org/10.1016/S0166-218X(00)00391-7.
  18. Roded Sharan. Graph Modification Problems and their Applications to Genomic Research. PhD thesis, Tel-Aviv University, Tel Aviv, Israel, 2002. Google Scholar
  19. E. S. Wolk. The comparability graph of a tree. Proceedings of the American Mathematical Society, 13:789-795, 1962. URL: https://doi.org/10.1090/S0002-9939-1962-0172273-0.
  20. Jing-Ho Yan, Jer-Jeong Chen, and Gerard Jennhwa Chang. Quasi-threshold graphs. Discrete Applied Mathematics, 69(3):247-255, 1996. URL: https://doi.org/10.1016/0166-218X(96)00094-7.
  21. Mihalis Yannakakis. Edge-deletion problems. SIAM Journal on Computing, 10(2):297-309, 1981. URL: https://doi.org/10.1137/0210021.
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