A Discharging Method: Improved Kernels for Edge Triangle Packing and Covering | SpringerLink
Skip to main content
Springer Nature Link
Log in

A Discharging Method: Improved Kernels for Edge Triangle Packing and Covering

  • Conference paper
  • First Online:
Computing and Combinatorics (COCOON 2023)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14423))

Included in the following conference series:

  • 551 Accesses

Abstract

Edge Triangle Packing and Edge Triangle Covering are dual problems extensively studied in the field of parameterized complexity. Given a graph G and an integer k, Edge Triangle Packing seeks to determine whether there exists a set of at least k edge-disjoint triangles in G, while Edge Triangle Covering aims to find out whether there exists a set of at most k edges that intersects all triangles in G. Previous research has shown that Edge Triangle Packing has a kernel of \((3+\epsilon )k\) vertices, while Edge Triangle Covering has a kernel of 6k vertices. In this paper, we show that the two problems allow kernels of 3k vertices, improving all previous results. A significant contribution of our work is the utilization of a novel discharging method for analyzing kernel size, which exhibits potential for analyzing other kernel algorithms.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 8464
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 10581
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, S. Saurabh, Parameterized Algorithms, Springer, 2015

    Google Scholar 

  2. Holyer, I.: The NP-completeness of some edge-partition problems. SIAM J. Comput. 10(4), 713–717 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  3. Kann, V.: Maximum bounded h-matching is MAX snp-complete. Inf. Process. Lett. 49(6), 309–318 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  4. Hurkens, C.A.J., Schrijver, A.: On the size of systems of sets every t of which have an sdr, with an application to the worst-case ratio of heuristics for packing problems. SIAM J. Discret. Math. 2(1), 68–72 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  5. Baker, B.S.: Approximation algorithms for np-complete problems on planar graphs. J. ACM 41(1), 153–180 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  6. L. Mathieson, E. Prieto-Rodriguez, P. Shaw, Packing edge disjoint triangles: A parameterized view, in: Parameterized and Exact Computation, First International Workshop, IWPEC 2004, Bergen, Norway, September 14–17, 2004, Proceedings, Vol. 3162 of Lecture Notes in Computer Science, Springer, 2004, pp. 127–137

    Google Scholar 

  7. Yang, Y.: Towards optimal kernel for edge-disjoint triangle packing. Inf. Process. Lett. 114(7), 344–348 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  8. Lin, W., Xiao, M.: A (3+\(\epsilon \))\({k}\)-vertex kernel for edge-disjoint triangle packing. Inf. Process. Lett. 142, 20–26 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  9. H. Yuan, Q. Feng, J. Wang, Improved kernels for triangle packing in tournaments, Sci. China Inf. Sci. 66 (5) (2023)

    Google Scholar 

  10. Brügmann, D., Komusiewicz, C., Moser, H.: On generating triangle-free graphs, Electron. Notes. Discret. Math. 32, 51–58 (2009)

    MATH  Google Scholar 

  11. F. K. H. A. Dehne, M. R. Fellows, F. A. Rosamond, P. Shaw, Greedy localization, iterative compression, modeled crown reductions: New FPT techniques, an improved algorithm for set splitting, and a novel 2k kernelization for vertex cover, in: Parameterized and Exact Computation, First International Workshop, IWPEC 2004, Bergen, Norway, September 14–17, 2004, Proceedings, Vol. 3162 of Lecture Notes in Computer Science, Springer, 2004, pp. 271–280

    Google Scholar 

  12. Xiao, M., Kou, S.: Parameterized algorithms and kernels for almost induced matching. Theor. Comput. Sci. 846, 103–113 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  13. M. Xiao, S. Kou, Kernelization and parameterized algorithms for 3-path vertex cover, in: Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Bern, Switzerland, April 20–22, 2017, Proceedings, Vol. 10185 of Lecture Notes in Computer Science, 2017, pp. 654–668

    Google Scholar 

  14. R. Cervený, P. Choudhary, O. Suchý, On kernels for d-path vertex cover, in: 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022, August 22–26, 2022, Vienna, Austria, Vol. 241 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, pp. 29:1–29:14

    Google Scholar 

Download references

Acknowledgments

The work is supported by the National Natural Science Foundation of China, under the grants 62372095 and 61972070.

Author information

Authors and Affiliations

  1. School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, China

    Zimo Sheng & Mingyu Xiao

Authors
  1. Zimo Sheng
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mingyu Xiao
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mingyu Xiao .

Editor information

Editors and Affiliations

  1. The University of Texas at Dallas, Richardson, TX, USA

    Weili Wu

  2. University of Delaware, Newark, DE, USA

    Guangmo Tong

Rights and permissions

Reprints and permissions

Copyright information

© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Sheng, Z., Xiao, M. (2024). A Discharging Method: Improved Kernels for Edge Triangle Packing and Covering. In: Wu, W., Tong, G. (eds) Computing and Combinatorics. COCOON 2023. Lecture Notes in Computer Science, vol 14423. Springer, Cham. https://doi.org/10.1007/978-3-031-49193-1_13

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-49193-1_13

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-49192-4

  • Online ISBN: 978-3-031-49193-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics