On the Feedback Number of 3-Uniform Linear Extremal Hypergraphs | SpringerLink
Skip to main content
Springer Nature Link
Log in

On the Feedback Number of 3-Uniform Linear Extremal Hypergraphs

  • Conference paper
  • First Online:
Combinatorial Optimization and Applications (COCOA 2021)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 13135))

Abstract

Let \(H=(V,E)\) be a hypergraph with vertex set V and edge set E. \(S\subseteq V\) is a feedback vertex set (FVS) of H if \(H{\setminus } S\) has no cycle and \(\tau _c(H)\) denote the minimum cardinality of a FVS of H. Chen et al. [IWOCA, 2016] has proven if H is a hypergraph with m edges, then \(\tau _c(H)\le m/3\). In this paper, we furthermore characterize all the extremal hypergraphs with \(\tau _c(H)= m/3\) holds.

Supported by National Natural Science Foundation of China under Grant No. 11901605, No. 11901292, No. 71801232, No. 12101069, the disciplinary funding of Central University of Finance and Economics, the Emerging Interdisciplinary Project of CUFE, the Fundamental Research Funds for the Central Universities and Innovation Foundation of BUPT for Youth (500421358).

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 12583
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 15729
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. Agrawal, A., Gupta, S., Saurabh, S., Sharma, R.: Improved algorithms and combinatorial bounds for independent feedback vertex set. In: Guo, J., Hermelin, D. (eds.) 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). LIPIcs, Aarhus, Denmark, vol. 63, pp. 2:1–2:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)

    Google Scholar 

  2. Alon, N., Spencer, J.H.: The Probabilistic Method. Wiley-Interscience Series in Discrete Mathematics and Optimization, 3rd edn. Wiley, New York (2008)

    Book  Google Scholar 

  3. Bafna, V., Berman, P., Fujito, T.: A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J. Discrete Math. 12(3), 289–297 (1999)

    Article  MathSciNet  Google Scholar 

  4. Bar-Yehuda, R., Geiger, D., Naor, J., Roth, R.M.: Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference. SIAM J. Comput. 27(4), 942–959 (1998)

    Article  MathSciNet  Google Scholar 

  5. Becker, A., Bar-Yehuda, R., Geiger, D.: Randomized algorithms for the loop cutset problem. J. Artif. Intell. Res. 12, 219–234 (2000)

    Article  MathSciNet  Google Scholar 

  6. Berge, C.: Hypergraphs - Combinatorics of Finite Sets. North-Holland Mathematical Library, vol. 45. North-Holland, Amsterdam (1989)

    MATH  Google Scholar 

  7. Brualdi, R.A.: Introductory Combinatorics, 5th edn. Pearson Education, London (2009)

    MATH  Google Scholar 

  8. Chen, J., Liu, Y., Lu, S., O’Sullivan, B., Razgon, I.: A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM 55(5), 21:1–21:19 (2008)

    Google Scholar 

  9. Chen, X., Diao, Z., Hu, X., Tang, Z.: Sufficient conditions for Tuza’s conjecture on packing and covering triangles. In: Mäkinen, V., Puglisi, S.J., Salmela, L. (eds.) IWOCA 2016. LNCS, vol. 9843, pp. 266–277. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-44543-4_21

    Chapter  Google Scholar 

  10. Chen, X., Diao, Z., Hu, X., Tang, Z.: Covering triangles in edge-weighted graphs. Theory Comput. Syst. 62(6), 1525–1552 (2018). https://doi.org/10.1007/s00224-018-9860-7

    Article  MathSciNet  MATH  Google Scholar 

  11. Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. In: Ostrovsky, R. (ed.) IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS 2011), Palm Springs, CA, USA, pp. 150–159. IEEE Computer Society (2011)

    Google Scholar 

  12. Dechter, R.: Enhancement schemes for constraint processing: backjumping, learning, and cutset decomposition. Artif. Intell. 41(3), 273–312 (1990)

    Article  MathSciNet  Google Scholar 

  13. Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Heidelberg (2012)

    MATH  Google Scholar 

  14. Erdös, P., Pósa, L.: On independent circuits contained in a graph. Can. J. Math. 17, 347–352 (1965)

    Article  MathSciNet  Google Scholar 

  15. Even, G., Naor, J.S., Schieber, B., Sudan, M.: Approximating minimum feedback sets and multi-cuts in directed graphs. In: Balas, E., Clausen, J. (eds.) IPCO 1995. LNCS, vol. 920, pp. 14–28. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-59408-6_38

    Chapter  Google Scholar 

  16. Festa, P., Pardalos, P.M., Resende, M.G.C.: Feedback set problems. In: Du, D.Z., Pardalos, P.M. (eds.) Handbook of Combinatorial Optimization, pp. 209–258. Springer, Boston (1999). https://doi.org/10.1007/978-1-4757-3023-4_4

    Chapter  Google Scholar 

  17. Fomin, F.V., Gaspers, S., Pyatkin, A.V., Razgon, I.: On the minimum feedback vertex set problem: exact and enumeration algorithms. Algorithmica 52(2), 293–307 (2008). https://doi.org/10.1007/s00453-007-9152-0

    Article  MathSciNet  MATH  Google Scholar 

  18. Fujito, T.: Approximating minimum feedback vertex sets in hypergraphs. Theor. Comput. Sci. 246(1–2), 107–116 (2000)

    Article  MathSciNet  Google Scholar 

  19. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)

    MATH  Google Scholar 

  20. Gupta, A., Lee, E., Li, J., Manurangsi, P., Wlodarczyk, M.: Losing treewidth by separating subsets. In: Chan, T.M. (ed.) Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), San Diego, California, USA, pp. 1731–1749. SIAM (2019)

    Google Scholar 

  21. Kenneth Brooks, R., Ernest Tilden, P.: Disproof of a conjecture of Erdös and Moser on tournaments. J. Comb. Theory 9(3), 225–238 (1970)

    Article  Google Scholar 

  22. Kim, E.J., Kwon, O.: Erdős-Pósa property of chordless cycles and its applications. J. Comb. Theory Ser. B 145, 65–112 (2020)

    Article  Google Scholar 

  23. Kociumaka, T., Pilipczuk, M.: Faster deterministic feedback vertex set. Inf. Process. Lett. 114(10), 556–560 (2014)

    Article  MathSciNet  Google Scholar 

  24. Neumann-Lara, V.: A short proof of a theorem of Reid and Parker on tournaments. Graphs Comb. 10(2–4), 363–366 (1994). https://doi.org/10.1007/BF02986686

    Article  MathSciNet  MATH  Google Scholar 

  25. Razgon, I.: Computing minimum directed feedback vertex set in o(1.9977\({}^{\text{n}}\)). In: Italiano, G.F., Moggi, E., Laura, L. (eds.) 10th Italian Conference on Theoretical Computer Science (ICTCS 2007), Rome, Italy, pp. 70–81. World Scientific (2007)

    Google Scholar 

  26. Reed, B.A., Robertson, N., Seymour, P.D., Thomas, R.: Packing directed circuits. Combinatorica 16(4), 535–554 (1996). https://doi.org/10.1007/BF01271272

    Article  MathSciNet  MATH  Google Scholar 

  27. Wang, C., Lloyd, E.L., Soffa, M.L.: Feedback vertex sets and cyclically reducible graphs. J. ACM 32(2), 296–313 (1985)

    Article  MathSciNet  Google Scholar 

  28. Xiao, M., Nagamochi, H.: An improved exact algorithm for undirected feedback vertex set. J. Comb. Optim. 30(2), 214–241 (2014). https://doi.org/10.1007/s10878-014-9737-x

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledges

The authors are very indebted to Professor Xujin Chen and Professor Xiaodong Hu for their invaluable suggestions and comments.

Author information

Authors and Affiliations

  1. School of Science, Beijing University of Posts and Telecommunications, Beijing, 100876, China

    Zhongzheng Tang

  2. Department of Mathematics, Nanjing University of Aeronautics and Astronautics, Nanjing, 211106, China

    Yucong Tang

  3. Key Laboratory of Mathematical Modelling and High Performance Computing of Air Vehicles (NUAA), MIIT, Nanjing, 211106, China

    Yucong Tang

  4. School of Statistics and Mathematics, Central University of Finance and Economics, Beijing, 100081, China

    Zhuo Diao

Authors
  1. Zhongzheng Tang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yucong Tang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Zhuo Diao
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zhuo Diao .

Editor information

Editors and Affiliations

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

    Ding-Zhu Du

  2. University of New Brunswick, Fredericton, NB, Canada

    Donglei Du

  3. Tianjin University of Technology, Tianjin, China

    Chenchen Wu

  4. Beijing University of Technology, Beijing, China

    Dachuan Xu

Rights and permissions

Reprints and permissions

Copyright information

© 2021 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Tang, Z., Tang, Y., Diao, Z. (2021). On the Feedback Number of 3-Uniform Linear Extremal Hypergraphs. In: Du, DZ., Du, D., Wu, C., Xu, D. (eds) Combinatorial Optimization and Applications. COCOA 2021. Lecture Notes in Computer Science(), vol 13135. Springer, Cham. https://doi.org/10.1007/978-3-030-92681-6_54

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-92681-6_54

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-92680-9

  • Online ISBN: 978-3-030-92681-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation