Document Open Access Logo

Space-Efficient Approximation Scheme for Maximum Matching in Sparse Graphs

Authors Samir Datta, Raghav Kulkarni, Anish Mukherjee

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.28.pdf
  • Filesize: 473 kB
  • 12 pages

Document Identifiers

Author Details

Samir Datta
Raghav Kulkarni
Anish Mukherjee

Cite As Get BibTex

Samir Datta, Raghav Kulkarni, and Anish Mukherjee. Space-Efficient Approximation Scheme for Maximum Matching in Sparse Graphs. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 28:1-28:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.MFCS.2016.28

Abstract

We present a Logspace Approximation Scheme (LSAS), i.e. an approximation algorithm for maximum matching in planar graphs (not necessarily bipartite) that achieves an approximation ratio arbitrarily close to one, using only logarithmic space. This deviates from the well known Baker's approach for approximation in planar graphs by avoiding the use of distance computation - which is not known to be in Logspace. Our algorithm actually works for any "recursively sparse" graph class which contains a linear size matching and also for certain other classes like bounded genus graphs.

The scheme is based on an LSAS in bounded degree graphs which are not known to be amenable to Baker's method. We solve the bounded degree case by parallel augmentation of short augmenting paths. Finding a large number of such disjoint paths can, in turn, be reduced to finding a large independent set in a bounded degree graph. The bounded degree assumption allows us to obtain a Logspace algorithm.

Subject Classification

Keywords
  • maximum matching
  • approximation scheme
  • logspace
  • planar graphs

Metrics

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

References

  1. Eric Allender, Klaus Reinhardt, and Shiyu Zhou. Isolation, matching, and counting: Uniform and nonuniform upper bounds. Journal of Computer and System Sciences, 59:164-181, 1999. Google Scholar
  2. Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, New York, NY, USA, 1st edition, 2009. Google Scholar
  3. Tetsuo Asano, David G. Kirkpatrick, Kotaro Nakagawa, and Osamu Watanabe. Õ(√n)-space and polynomial-time algorithm for planar directed graph reachability. In Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II, pages 45-56, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44465-8_5.
  4. Brenda S. Baker. Approximation algorithms for np-complete problems on planar graphs. J. ACM, 41(1):153-180, 1994. URL: http://dx.doi.org/10.1145/174644.174650.
  5. Greg Barnes, Jonathan F. Buss, Walter L. Ruzzo, and Baruch Schieber. A sublinear space, polynomial time algorithm for directed s-t connectivity. SIAM J. Comput., 27(5):1273-1282, 1998. URL: http://dx.doi.org/10.1137/S0097539793283151.
  6. Therese C. Biedl. Linear reductions of maximum matching. In Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, January 7-9, 2001, Washington, DC, USA., pages 825-826, 2001. URL: http://dl.acm.org/citation.cfm?id=365411.365789.
  7. Therese C. Biedl, Erik D. Demaine, Christian A. Duncan, Rudolf Fleischer, and Stephen G. Kobourov. Tight bounds on maximal and maximum matchings. Discrete Mathematics, 285(1-3):7-15, 2004. URL: http://dx.doi.org/10.1016/j.disc.2004.05.003.
  8. Ashok K. Chandra, Larry Stockmeyer, and Uzi Vishkin. Constant depth reducibility. SIAM Journal on Computing, 13(2):423-439, 1984. URL: http://dx.doi.org/10.1137/0213028.
  9. Samir Datta and Raghav Kulkarni. Space complexity of optimization problems in planar graphs. In Theory and Applications of Models of Computation - 11th Annual Conference, TAMC 2014, Chennai, India, April 11-13, 2014. Proceedings, pages 300-311, 2014. URL: http://dx.doi.org/10.1007/978-3-319-06089-7_21.
  10. Samir Datta, Raghav Kulkarni, Nutan Limaye, and Meena Mahajan. Planarity, determinants, permanents, and (unique) matchings. ACM Trans. Comput. Theory, 1(3):1-20, 2010. URL: http://dx.doi.org/10.1145/1714450.1714453.
  11. Samir Datta, Raghav Kulkarni, and Sambuddha Roy. Deterministically isolating a perfect matching in bipartite planar graphs. Theory of Computing Systems, 47:737-757, 2010. URL: http://dx.doi.org/10.1007/s00224-009-9204-8.
  12. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  13. Ran Duan and Seth Pettie. Linear-time approximation for maximum weight matching. J. ACM, 61(1):1:1-1:23, 2014. URL: http://dx.doi.org/10.1145/2529989.
  14. J. Edmonds. Paths, trees and flowers. Canad. J. Math., 17:449-467, 1965. Google Scholar
  15. David Eppstein. Sparser bipartite graphs? Theoretical Computer Science Stack Exchange. URL: http://cstheory.stackexchange.com/q/31567.
  16. Thanh Minh Hoang. On the matching problem for special graph classes. In IEEE Conference on Computational Complexity, pages 139-150, 2010. URL: http://dx.doi.org/10.1109/CCC.2010.21.
  17. 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. URL: http://dx.doi.org/10.1137/0202019.
  18. Stefan Hougardy and Doratha E. Drake Vinkemeier. Approximating weighted matchings in parallel. Inf. Process. Lett., 99(3):119-123, 2006. URL: http://dx.doi.org/10.1016/j.ipl.2006.03.005.
  19. Tatsuya Imai, Kotaro Nakagawa, Aduri Pavan, N. V. Vinodchandran, and Osamu Watanabe. An o(nonehalf+∑)-space and polynomial-time algorithm for directed planar reachability. In Proceedings of the 28th Conference on Computational Complexity, CCC 2013, K.lo Alto, California, USA, 5-7 June, 2013, pages 277-286, 2013. URL: http://dx.doi.org/10.1109/CCC.2013.35.
  20. Richard M. Karp, Eli Upfal, and Avi Wigderson. Constructing a perfect matching is in random NC. Combinatorica, 6(1):35-48, 1986. URL: http://dx.doi.org/10.1007/BF02579407.
  21. P. W. Kasteleyn. Graph theory and crystal physics. Graph Theory and Theoretical Physics, 1:43-110, 1967. Google Scholar
  22. Raghav Kulkarni. On the power of isolation in planar graphs. Technical Report TR09-024, Electronic Colloquium on Computational Complexity, 2009. Google Scholar
  23. Raghav Kulkarni, Meena Mahajan, and Kasturi R. Varadarajan. Some perfect matchings and perfect half-integral matchings in NC. Chicago Journal of Theoretical Computer Science, 2008(4), September 2008. Google Scholar
  24. L. Lovász and M.D. Plummer. Matching Theory, volume 29. North-Holland Publishing Co, 1986. Google Scholar
  25. Meena Mahajan and Kasturi R. Varadarajan. A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract). In STOC, pages 351-357, 2000. Google Scholar
  26. Gary L. Miller and Joseph Naor. Flow in planar graphs with multiple sources and sinks. SIAM J. Comput., 24(5):1002-1017, 1995. Google Scholar
  27. Ketan Mulmuley, Umesh Vazirani, and Vijay Vazirani. Matching is as easy as matrix inversion. Combinatorica, 7:105-113, 1987. Google Scholar
  28. Jaroslav Nesetril and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-27875-4.
  29. Omer Reingold. Undirected connectivity in log-space. J. ACM, 55(4), 2008. URL: http://dx.doi.org/10.1145/1391289.1391291.
  30. Walter J. Savitch. Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci., 4(2):177-192, 1970. URL: http://dx.doi.org/10.1016/S0022-0000(70)80006-X.
  31. Till Tantau. Logspace optimization problems and their approximability properties. Theory Comput. Syst., 41(2):327-350, 2007. URL: http://dx.doi.org/10.1007/s00224-007-2011-1.
  32. Leslie G. Valiant. The complexity of computing the permanent. Theor. Comput. Sci., 8:189-201, 1979. Google Scholar
  33. Vijay Vazirani. NC algorithms for computing the number of perfect matchings in k_3,3-free graphs and related problems. In Proceedings of SWAT '88, pages 233-242, 1988. Google Scholar
  34. Heribert Vollmer. Introduction to Circuit Complexity: A Uniform Approach. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 1999. Google Scholar
  35. Douglas B. West. Introduction to Graph Theory. Prentice Hall, 2 edition, September 2000. Google Scholar
  36. Tomoyuki Yamakami. Combinatorial Optimization and Applications: 7th International Conference, COCOA 2013, Chengdu, China, December 12-14, 2013, Proceedings, chapter Uniform-Circuit and Logarithmic-Space Approximations of Refined Combinatorial Optimization Problems, pages 318-329. Springer International Publishing, Cham, 2013. URL: http://dx.doi.org/10.1007/978-3-319-03780-6_28.
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 About DROPS Imprint Privacy Contact