(Sub)linear Kernels for Edge Modification Problems Towards Structured Graph Classes

Authors Gabriel Bathie, Nicolas Bousquet, Théo Pierron



PDF
Thumbnail PDF

File

LIPIcs.IPEC.2021.8.pdf
  • Filesize: 0.68 MB
  • 14 pages

Document Identifiers

Author Details

Gabriel Bathie
  • École Normale Supérieure de Lyon, France
Nicolas Bousquet
  • LIRIS, CNRS, Université Claude Bernard Lyon 1, Université de Lyon, France
Théo Pierron
  • LIRIS, CNRS, Université Claude Bernard Lyon 1, Université de Lyon, France

Cite AsGet BibTex

Gabriel Bathie, Nicolas Bousquet, and Théo Pierron. (Sub)linear Kernels for Edge Modification Problems Towards Structured Graph Classes. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.IPEC.2021.8

Abstract

In a (parameterized) graph edge modification problem, we are given a graph G, an integer k and a (usually well-structured) class of graphs 𝒢, and ask whether it is possible to transform G into a graph G' ∈ 𝒢 by adding and/or removing at most k edges. Parameterized graph edge modification problems received considerable attention in the last decades. In this paper, we focus on finding small kernels for edge modification problems. One of the most studied problems is the Cluster Editing problem, in which the goal is to partition the vertex set into a disjoint union of cliques. Even if this problem admits a 2k kernel [Cao and Chen, 2012], this kernel does not reduce the size of most instances. Therefore, we explore the question of whether linear kernels are a theoretical limit in edge modification problems, in particular when the target graphs are very structured (such as a partition into cliques for instance). We prove, as far as we know, the first sublinear kernel for an edge modification problem. Namely, we show that Clique + Independent Set Deletion, which is a restriction of Cluster Deletion, admits a kernel of size O(k/log k). We also obtain small kernels for several other edge modification problems. We prove that Split Addition (and the equivalent Split Deletion) admits a linear kernel, improving the existing quadratic kernel of Ghosh et al. [Ghosh et al., 2015]. We complement this result by proving that Trivially Perfect Addition admits a quadratic kernel (improving the cubic kernel of Guo [Guo, 2007]), and finally prove that its triangle-free version (Starforest Deletion) admits a linear kernel, which is optimal under ETH.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • kernelization
  • graph editing
  • split graphs
  • (sub)linear kernels

Metrics

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

References

  1. Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. Machine learning, 56(1):89-113, 2004. Google Scholar
  2. Amir Ben-Dor, Ron Shamir, and Zohar Yakhini. Clustering gene expression patterns. Journal of computational biology, 6(3-4):281-297, 1999. Google Scholar
  3. Ivan Bliznets, Marek Cygan, Pawel Komosa, Lukáš Mach, and Michał Pilipczuk. Lower bounds for the parameterized complexity of minimum fill-in and other completion problems. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1132-1151. SIAM, 2016. Google Scholar
  4. Sebastian Böcker. A golden ratio parameterized algorithm for cluster editing. Journal of Discrete Algorithms, 16:79-89, 2012. Google Scholar
  5. Pablo Burzyn, Flavia Bonomo, and Guillermo Durán. Np-completeness results for edge modification problems. Discrete Applied Mathematics, 154(13):1824-1844, 2006. Google Scholar
  6. Leizhen Cai. Fixed-parameter tractability of graph modification problems for hereditary properties. Information Processing Letters, 58(4):171-176, 1996. Google Scholar
  7. Yixin Cao and Jianer Chen. Cluster editing: Kernelization based on edge cuts. Algorithmica, 64(1):152-169, 2012. Google Scholar
  8. Yixin Cao and Yuping Ke. Improved kernels for edge modification problems. arXiv preprint arXiv:2104.14510, 2021. Google Scholar
  9. Jianer Chen and Jie Meng. A 2k kernel for the cluster editing problem. Journal of Computer and System Sciences, 78(1):211-220, 2012. Google Scholar
  10. 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 preprint arXiv:2001.06867, 2020. Google Scholar
  11. 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
  12. Peter Damaschke and Olof Mogren. Editing the simplest graphs. In International Workshop on Algorithms and Computation, pages 249-260. Springer, 2014. Google Scholar
  13. 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. Google Scholar
  14. Pål Grønås Drange and Michał Pilipczuk. A polynomial kernel for trivially perfect editing. Algorithmica, 80(12):3481-3524, 2018. Google Scholar
  15. Pål Grønås Drange, Felix Reidl, Fernando Sánchez Villaamil, and Somnath Sikdar. Fast biclustering by dual parameterization. arXiv preprint arXiv:1507.08158, 2015. Google Scholar
  16. Mael Dumas, Anthony Perez, and Ioan Todinca. A cubic kernel for trivially perfect edition. private communication. Google Scholar
  17. Fedor V Fomin, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, and Yngve Villanger. Tight bounds for parameterized complexity of cluster editing with a small number of clusters. Journal of Computer and System Sciences, 80(7):1430-1447, 2014. Google Scholar
  18. Fedor V Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Kernelization: theory of parameterized preprocessing. Cambridge University Press, 2019. Google Scholar
  19. Esha Ghosh, Sudeshna Kolay, Mrinal Kumar, Pranabendu Misra, Fahad Panolan, Ashutosh Rai, and MS Ramanujan. Faster parameterized algorithms for deletion to split graphs. Algorithmica, 71(4):989-1006, 2015. Google Scholar
  20. Jens Gramm, Jiong Guo, Falk Hüffner, and Rolf Niedermeier. Graph-modeled data clustering: Exact algorithms for clique generation. Theory of Computing Systems, 38(4):373-392, 2005. Google Scholar
  21. Jiong Guo. Problem kernels for np-complete edge deletion problems: Split and related graphs. In International Symposium on Algorithms and Computation, pages 915-926. Springer, 2007. Google Scholar
  22. Peter L Hammer and Bruno Simeone. The splittance of a graph. Combinatorica, 1(3):275-284, 1981. Google Scholar
  23. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. Journal of Computer and System Sciences, 62(2):367-375, 2001. Google Scholar
  24. Yunlong Liu, Jianxin Wang, Jie You, Jianer Chen, and Yixin Cao. Edge deletion problems: Branching facilitated by modular decomposition. Theoretical Computer Science, 573:63-70, 2015. Google Scholar
  25. Federico Mancini. Graph modification problems related to graph classes. PhD degree dissertation, University of Bergen Norway, 2, 2008. Google Scholar
  26. Assaf Natanzon, Ron Shamir, and Roded Sharan. Complexity classification of some edge modification problems. Discrete Applied Mathematics, 113(1):109-128, 2001. Google Scholar
  27. René van Bevern, Vincent Froese, and Christian Komusiewicz. Parameterizing edge modification problems above lower bounds. Theory of Computing Systems, 62(3):739-770, 2018. Google Scholar
  28. Zhenyu Wu and Richard Leahy. An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation. IEEE transactions on pattern analysis and machine intelligence, 15(11):1101-1113, 1993. Google Scholar
  29. Mihalis Yannakakis. Node-and edge-deletion np-complete problems. In Proceedings of the tenth annual ACM symposium on Theory of computing, pages 253-264, 1978. Google Scholar
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