Document Open Access Logo

New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition

Authors Qilong Feng, Guanlan Tan, Senmin Zhu, Bin Fu, Jianxin Wang

PDF

File

Thumbnail PDF
PDF
LIPIcs.ISAAC.2018.31.pdf
  • Filesize: 413 kB
  • 12 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Mathematics of computing → Approximation algorithms
Keywords
  • König-Egerváry graph
  • Gallai-Edmonds decomposition

Metrics

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

Abstract

König-Egerváry graphs form an important graph class which has been studied extensively in graph theory. Much attention has also been paid on König-Egerváry subgraphs and König-Egerváry graph modification problems. In this paper, we focus on one König-Egerváry subgraph problem, called the Maximum Edge Induced König Subgraph problem. By exploiting the classical Gallai-Edmonds decomposition, we establish connections between minimum vertex cover, Gallai-Edmonds decomposition structure, maximum matching, maximum bisection, and König-Egerváry subgraph structure. We obtain a new structural property of König-Egerváry subgraph: every graph G=(V, E) has an edge induced König-Egerváry subgraph with at least 2|E|/3 edges. Based on the new structural property proposed, an approximation algorithm with ratio 10/7 for the Maximum Edge Induced König Subgraph problem is presented, improving the current best ratio of 5/3. To the best of our knowledge, this paper is the first one establishing the connection between Gallai-Edmonds decomposition and König-Egerváry graphs. Using 2|E|/3 as a lower bound, we define the Edge Induced König Subgraph above lower bound problem, and give a kernel of at most 30k edges for the problem.

Cite As Get BibTex

Qilong Feng, Guanlan Tan, Senmin Zhu, Bin Fu, and Jianxin Wang. New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 31:1-31:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ISAAC.2018.31

Author Details

Qilong Feng
  • School of Information Science and Engineering, Central South University, Changsha, P.R. China
Guanlan Tan
  • School of Information Science and Engineering, Central South University, Changsha, P.R. China
Senmin Zhu
  • School of Information Science and Engineering, Central South University, Changsha, P.R. China
Bin Fu
  • Department of Computer Science, University of Texas-Rio Grande Valley, USA
Jianxin Wang
  • School of Information Science and Engineering, Central South University, Changsha, P.R. China

Funding

This work is supported by the National Natural Science Foundation of China under Grants (61420106009, 61872450, 61828205, 61672536).

References

  1. John A.Bondy and U. S. R. Murty. Graph Theory with Applications. North Holland, 1976. Google Scholar
  2. Miklós Bartha and Miklós Krész. Molecular Switching by Turing Automata. In Proceedings of 3rd Workshop on Non-Classical Models for Automata and Application(NCMA), pages 51-71, 2011. Google Scholar
  3. Francis Bloch, Bhaskar Dutta, and Mihai Manea. Efficient Partnership Formation In Networks. Warwick Economics Research Paper, 2018. Google Scholar
  4. Flavia Bonomo, Mitre C. Dourado, Guillermo Durán, Luerbio Faria, Luciano N. Grippo, and Martín D. Safe. Forbidden subgraphs and the König-Egerváry property. Discrete Applied Mathematics, 161(16-17):2380-2388, 2013. Google Scholar
  5. Jean Marie. Bourjolly and William R. Pulleyblank. König-Egerváry graphs, 2-bicritical raphs and fractional matchings. Discrete Applied Mathematics, 24(1):63-82, 1989. Google Scholar
  6. Domingos M. Cardoso, Maria Robbiano, and Oscar Rojo. Combinatorial and spectral properties of König-Egerváry graphs. Discrete Applied Mathematics, 217:446-454, 2017. Google Scholar
  7. Jianer Chen and I. A. Kanj. Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms. Journal of Computer and System Sciences, 67(4):833-847, 2003. Google Scholar
  8. Jianer Chen, I A. Kanj, and Ge Xia. Improved parameterized upper bounds for vertex cover. In Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science(MFCS), pages 238-249, 2006. Google Scholar
  9. Marek Cygan, Marcin Pilipczuk, and Jakub Onufry. Wojtaszczyk. On multiway cut parameterized above lower bounds. ACM Transactions on Computation Theory, 5(1):1-11, 2013. Google Scholar
  10. Robert W. Deming. Independence numbers of graphs—an extension of the König-Egerváry theorem. Discrete Mathematics, 27(1):23-33, 1979. Google Scholar
  11. Zakir Deniz, Tınaz Ekim, Tatiana Romina. Hartinger, Martin Milanič, and Mordechai Shalom. On two extensions of equimatchable graphs. Discrete Optimization, 26:112-130, 2017. Google Scholar
  12. Jack Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics, 17(3):449-467, 1965. Google Scholar
  13. Qilong Feng, Senmin Zhu, and Jianxin Wang. A New Kernel for Parameterized Max-Bisection Above Tight Lower Bound. In Proceedings of the 23rd Annual International Computing and Combinatorics Conference(COCOON), pages 188-199, 2017. Google Scholar
  14. Toshihiro Fujito and Hiroshi Nagamochi. A 2-approximation algorithm for the minimum weight edge dominating set problem. Discrete Applied Mathematics, 118(3):199-207, 2002. Google Scholar
  15. Shivam Garg and Geevarghese Philip. Raising the bar for vertex cover: fixed-parameter tractability above a higher guarantee. In Proceedings of the 27th annual ACM-SIAM Symposium on Discrete Algorithms(SODA), pages 1152-1166, 2016. Google Scholar
  16. David J. Haglin and Shankar M. Venkatesan. Approximation and intractability results for the maximum cut problem and its variants. IEEE Transactions on Computers, 40(1):110-113, 1991. Google Scholar
  17. Adi Jarden, Vadim E. Levit, and Eugen Mandrescu. Two more characterizations of König-Egerváry graphs. Discrete Applied Mathematics, 231:175-180, 2017. Google Scholar
  18. Bo Ji and Yu Sang. Throughput characterization of node-based scheduling in multihop wireless networks: A novel application of the gallai-edmonds structure theorem. In Proceedings of the 17th ACM International Symposium on Mobile Ad Hoc Networking and Computing(MobiHoc), pages 41-50, 2016. Google Scholar
  19. Richard M. Karp. Reducibility Among Combinatorial Problems. In Proceedings of a symposium on the Complexity of Computer Computations, pages 85-103, 1972. Google Scholar
  20. Ephraim Korach, Thanh Nguyen, and Britta Peis. Subgraph characterization of red/blue-split graph and kőnig egerváry graphs. In Proceedings of the 17th annual ACM-SIAM Symposium on Discrete Algorithm(SODA), pages 842-850, 2006. Google Scholar
  21. Stefan Kratsch. A randomized polynomial kernelization for vertex cover with a smaller parameter. arXiv preprint, 2016. URL: http://arxiv.org/abs/1611.06795.
  22. Michael Lampis. A kernel of order 2k-clogk for vertex cover. Information Processing Letters, 111(23-24):1089-1091, 2011. Google Scholar
  23. Vadim E. Levit and Eugen Mandrescu. Critical independent sets and König-Egerváry graphs. Graphs and Combinatorics, 28(2):243-250, 2012. Google Scholar
  24. Vadim E. Levit and Eugen Mandrescu. On maximum matchings in König-Egerváry graphs. Discrete Applied Mathematics, 161(10-11):1635-1638, 2013. Google Scholar
  25. Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh. Faster parameterized algorithms using linear programming. ACM Transactions on Algorithms, 11(2):15, 2014. Google Scholar
  26. László Lovász. Ear-decompositions of matching-covered graphs. Combinatorica, 3(1):105-117, 1983. Google Scholar
  27. László Lovász and Michael D. Plummer. Matching Theory. North-Holland, Amsterdam, 1986. Google Scholar
  28. Eric Mcdermid. A 3/2-approximation algorithm for general stable marriage. In Proceedings of the 36th International Colloquium on Automata, Languages, and Programming(ICALP), pages 689-700, 2009. Google Scholar
  29. Sounaka Mishra, Shijin Rajakrishnan, and Saket Saurabh. On approximability of optimization problems related to Red/Blue-split graphs. Theoretical Computer Science, 690:104-113, 2017. Google Scholar
  30. Sounaka Mishra, Venkatesh Raman, Saket Saurabh, and Somnath Sikdar. König deletion sets and vertex covers above the matching size. In Proceedings of the 19th International Symposium on Algorithms and Computation(ISAAC), pages 836-847, 2008. Google Scholar
  31. Sounaka Mishra, Venkatesh Raman, Saket Saurabh, Somnath Sikdar, and C. R. Subramanian. The complexity of finding subgraphs whose matching number equals the vertex cover number. In Proceedings of the 18th International Symposium on Algorithms and Computation(ISAAC), pages 268-279, 2007. Google Scholar
  32. Sounaka Mishra, Venkatesh Raman, Saket Saurabh, Somnath Sikdar, and C. R. Subramanian. The complexity of König subgraph problems and above-guarantee vertex cover. Algorithmica, 61(4):857-881, 2011. Google Scholar
  33. Matthias Mnich and Rico Zenklusen. Bisections above tight lower bounds. In Proceedings of the 38th International Workshop on Graph-Theoretic Concepts in Computer Science(WG), pages 184-193, 2012. Google Scholar
  34. N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh. LP can be a cure for parameterized problems. In Proceedings of the 29th Internatinal Symposium on Theoretical Aspects of Computer Science(STACS)), pages 338-349, 2012. Google Scholar
  35. Ojas Parekh. Edge dominating and hypomatchable sets. In Proceedings of the 13th annual ACM-SIAM Symposium on Discrete Algorithms(SODA), pages 287-291, 2002. Google Scholar
  36. Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh. Paths, flowers and vertex cover. In Proceedings of the 19th Annual European Symposium on Algorithms(ESA), pages 382-393, 2011. Google Scholar
  37. Igor Razgon and Barry O'Sullivan. Almost 2-SAT is fixed-parameter tractable. Journal of Computer and System Sciences, 75(8):435-450, 2009. Google Scholar
  38. Tayfun Sönmez and M Utku. Ünver. Altruistically unbalanced kidney exchange. Journal of Economic Theory, 152:105-129, 2014. Google Scholar
  39. F. Stersoul. A characterization of the graphs in which the transversal number equals the matching number. Journal of Combinatorial Theory, Series B, 27(2):228-229, 1979. Google Scholar
  40. C. R. Subramanian. Vertex covers: parameterizing above the requirement. IMSc Technical Report, 2001. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact