Document Open Access Logo

Maintaining Approximate Maximum Matching in an Incremental Bipartite Graph in Polylogarithmic Update Time

Author Manoj Gupta

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2014.227.pdf
  • Filesize: 0.53 MB
  • 13 pages

Document Identifiers

Author Details

Manoj Gupta

Cite AsGet BibTex

Manoj Gupta. Maintaining Approximate Maximum Matching in an Incremental Bipartite Graph in Polylogarithmic Update Time. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 227-239, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
https://doi.org/10.4230/LIPIcs.FSTTCS.2014.227

Abstract

A sparse subgraph G' of G is called a matching sparsifier if the size or weight of matching in G' is approximately equal to the size or weight of maximum matching in G. Recently, algorithms have been developed to find matching sparsifiers in a static bipartite graph. In this paper, we show that we can find matching sparsifier even in an incremental bipartite graph. This observation leads to following results: 1. We design an algorithm that maintains a (1+epsilon) approximate matching in an incremental bipartite graph in O(log^2(n) / (epsilon^{4}) update time. 2. For weighted graphs, we design an algorithm that maintains (1+epsilon) approximate weighted matching in O((log(n)*log(n*N)) / (epsilon^4) update time where \maxweight is the maximum weight of any edge in the graph.
Keywords
  • Graph Algorithm
  • Dynamic Graph

Metrics

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

References

  1. Kook Jin Ahn and Sudipto Guha. Linear programming in the semi-streaming model with application to the maximum matching problem. Inf. Comput., 222:59-79, 2013. Google Scholar
  2. Abhash Anand, Surender Baswana, Manoj Gupta, and Sandeep Sen. Maintaining Approximate Maximum Weighted Matching in Fully Dynamic Graphs. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012), volume 18 of Leibniz International Proceedings in Informatics (LIPIcs), pages 257-266, Dagstuhl, Germany, 2012. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Google Scholar
  3. Abhash Anand, Surender Baswana, Manoj Gupta, and Sandeep Sen. Maintaining approximate maximum weighted matching in fully dynamic graphs. CoRR, abs/1207.3976, 2012. Google Scholar
  4. Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta-algorithm and applications. Theory of Computing, 8(1):121-164, 2012. Google Scholar
  5. S. Baswana, M. Gupta, and S. Sen. Fully dynamic maximal matching in O(log n) update time. In Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on, pages 383-392. IEEE, 2011. Google Scholar
  6. Ran Duan and Seth Pettie. Linear-time approximation for maximum weight matching. J. ACM, 61(1):1:1-1:23, January 2014. Google Scholar
  7. Ran Duan, Seth Pettie, and Hsin-Hao Su. Scaling algorithms for approximate and exact maximum weight matching. CoRR, abs/1112.0790, 2011. Google Scholar
  8. Sebastian Eggert, Lasse Kliemann, Peter Munstermann, and Anand Srivastav. Bipartite matching in the semi-streaming model. Algorithmica, 63(1-2):490-508, June 2012. Google Scholar
  9. Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. On graph problems in a semi-streaming model. Theor. Comput. Sci., 348(2):207-216, December 2005. Google Scholar
  10. Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. Graph distances in the data-stream model. SIAM J. Comput., 38(5):1709-1727, December 2008. Google Scholar
  11. Manoj Gupta and Richard Peng. Fully dynamic (1+ε)-approximate matchings. In 54th Annual IEEE Symposium on Foundations of Computer Science, 2013. Google Scholar
  12. John E. Hopcroft and Richard M. Karp. An n^5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput., 2(4):225-231, 1973. Google Scholar
  13. Zoran Ivkovic and Errol L. Lloyd. Fully dynamic maintenance of vertex cover. In WG '93: Proceedings of the 19th International Workshop on Graph-Theoretic Concepts in Computer Science, pages 99-111, London, UK, 1994. Springer-Verlag. Google Scholar
  14. S. Micali and V.V. Vazirani. An O(√|V||E|) algorithm for finding maximum matching in general graphs. In Foundations of Computer Science, 1980., 21st Annual Symposium on, pages 17-27. IEEE, 1980. Google Scholar
  15. Ofer Neiman and Shay Solomon. Deterministic algorithms for fully dynamic maximal matching. CoRR, abs/1207.1277, 2012. Google Scholar
  16. Krzysztof Onak and Ronitt Rubinfeld. Maintaining a large matching and a small vertex cover. In STOC, pages 457-464, 2010. Google Scholar
  17. Piotr Sankowski. Faster dynamic matchings and vertex connectivity. In SODA, pages 118-126, 2007. Google Scholar
  18. Vijay V. Vazirani. An improved definition of blossoms and a simpler proof of the MV matching algorithm. CoRR, abs/1210.4594, 2012. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact