Document Open Access Logo

NC Algorithms for Weighted Planar Perfect Matching and Related Problems

Author Piotr Sankowski

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.97.pdf
  • Filesize: 0.5 MB
  • 16 pages

Document Identifiers

Author Details

Piotr Sankowski
  • Institute of Informatics, University of Warsaw

Cite AsGet BibTex

Piotr Sankowski. NC Algorithms for Weighted Planar Perfect Matching and Related Problems. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 97:1-97:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.97

Abstract

Consider a planar graph G=(V,E) with polynomially bounded edge weight function w:E -> [0, poly(n)]. The main results of this paper are NC algorithms for finding minimum weight perfect matching in G. In order to solve this problems we develop a new relatively simple but versatile framework that is combinatorial in spirit. It handles the combinatorial structure of matchings directly and needs to only know weights of appropriately defined matchings from algebraic subroutines. Moreover, using novel planarity preserving reductions, we show how to find: maximum weight matching in G when G is bipartite; maximum multiple-source multiple-sink flow in G where c:E -> [1, poly(n)] is a polynomially bounded edge capacity function; minimum weight f-factor in G where f:V -> [1, poly(n)]; min-cost flow in G where c:E -> [1, poly(n)] is a polynomially bounded edge capacity function and b:V -> [1, poly(n)] is a polynomially bounded vertex demand function. There have been no known NC algorithms for these problems previously.

Subject Classification

ACM Subject Classification
  • Theory of computation → Network flows
  • Theory of computation → Shared memory algorithms
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • planar graph
  • NC algorithms
  • maximum cardinality matching
  • maximum weight matching
  • min-cost flow
  • maximum multiple-source multiple-sink flow
  • f-factors

Metrics

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

Related Versions

References

  1. Manindra Agrawal, Thanh Minh Hoang, and Thomas Thierauf. The polynomially bounded perfect matching problem is in NC2. In Proceedings of the 24th Annual Conference on Theoretical Aspects of Computer Science, STACS'07, pages 489-499, Berlin, Heidelberg, 2007. Springer-Verlag. Google Scholar
  2. Nima Anari and Vijay V. Vazirani. Planar graph perfect matching is in NC, 2017. URL: http://arxiv.org/abs/arXiv:1709.07822.
  3. R.P. Anstee. A polynomial algorithm for b-matching: An alternative approach. IPL, 24:153-157, 1987. Google Scholar
  4. G. Borradaile, P. N. Klein, S. Mozes, Y. Nussbaum, and C. Wulff-Nilsen. Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time. In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, FOCS '11, pages 170-179, Oct 2011. Google Scholar
  5. K.W. Chong and T.W. Lam. Finding Connected Components in O(log n log log n) Time on the EREW PRAM. Journal of Algorithms, 18(3):378-402, 1995. Google Scholar
  6. L. Csanky. Fast Parallel Matrix Inversion Algorithms. SIAM Journal on Computing, 5(4):618-623, 1976. Google Scholar
  7. Marek Cygan, Harold N. Gabow, and Piotr Sankowski. Algorithmic Applications of Baur-Strassen’s Theorem: Shortest Cycles, Diameter, and Matchings. J. ACM, 62(4):28:1-28:30, 2015. Google Scholar
  8. Samir Datta, Arjun Gopalan, Raghav Kulkarni, and Raghunath Tewari. Improved Bounds for Bipartite Matching on Surfaces. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), volume 14 of LIPIcs, pages 254-265, Dagstuhl, Germany, 2012. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Google Scholar
  9. Samir Datta, Raghav Kulkarni, and Sambuddha Roy. Deterministically isolating a perfect matching in bipartite planar graphs. Theory of Computing Systems, 47(3):737-757, Oct 2010. Google Scholar
  10. Jack Edmonds. Maximum matching and a polyhedron with 0,1-vertices. Journal of Research National Bureau of Standards-B.,, 69B:125-130, 1965. Google Scholar
  11. Jittat Fakcharoenphol and Satish Rao. Planar graphs, negative weight edges, shortest paths, and near linear time. Journal of Computer and System Sciences, 72(5):868-889, 2006. Special Issue on FOCS 2001. Google Scholar
  12. Stephen Fenner, Rohit Gurjar, and Thomas Thierauf. Bipartite perfect matching is in quasi-nc. In Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, STOC '16, pages 754-763, New York, NY, USA, 2016. ACM. Google Scholar
  13. H. N. Gabow and P. Sankowski. Algebraic algorithms for b-matching, shortest undirected paths, and f-factors. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS '13, pages 137-146, Oct 2013. Google Scholar
  14. Harold Gabow and Robert Tarjan. Almost-optimum speed-ups of algorithms for bipartite matching and related problems. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC '88, pages 514-527, New York, NY, USA, 1988. ACM. Google Scholar
  15. Harold N. Gabow. An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, STOC '83, pages 448-456, New York, NY, USA, 1983. ACM. Google Scholar
  16. Harold N. Gabow. A combinatoric interpretation of dual variables for weighted matching and f-factors. Theor. Comput. Sci., 454:136-163, 2012. Google Scholar
  17. Zvi Galil and Victor Y. Pan. Improved processor bounds for combinatorial problems in RNC. Combinatorica, 8(2):189-200, 1988. Google Scholar
  18. A. V. Goldberg, S. A. Plotkin, and P. M. Vaidya. Sublinear-time parallel algorithms for matching and related problems. In Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, FOCS '88, pages 174-185, Oct 1988. Google Scholar
  19. A. V. Goldberg, D. B. Shmoys, S. A. Plotkin, and E. Tardos. Interior-point methods in parallel computation. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science, FOCS '89, pages 350-355, Washington, DC, USA, 1989. IEEE Computer Society. Google Scholar
  20. Shafi Goldwasser and Ofer Grossman. Bipartite Perfect Matching in Pseudo-Deterministic NC. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), volume 80 of LIPIcs, pages 87:1-87:13, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Google Scholar
  21. Michał Hańćkowiak, Michał Karoński, and Alessandro Panconesi. On the distributed complexity of computing maximal matchings. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '98, pages 219-225, Philadelphia, PA, USA, 1998. Society for Industrial and Applied Mathematics. Google Scholar
  22. T. M. Hoang. On the matching problem for special graph classes. In Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC '10, pages 139-150, June 2010. Google Scholar
  23. Howard J. Karloff. A Las Vegas RNC algorithm for maximum matching. Combinatorica, 6(4):387-391, 1986. Google Scholar
  24. Richard M. Karp, Eli Upfal, and Avi Wigderson. Constructing a perfect matching is in random NC. Combinatorica, 6(1):35-48, 1986. Google Scholar
  25. P. W. Kasteleyn. Dimer statistics and phase transitions. Journal of Mathematical Physics, 4(2):287-293, 1963. Google Scholar
  26. Arpita Korwar. Finding an NC algorithm for perfect matching in planar graphs. Master’s thesis, IIT Kanpur, 2009. Google Scholar
  27. Raghav Kulkarni and Meena Mahajan. Seeking a vertex of the planar matching polytope in nc. In Susanne Albers and Tomasz Radzik, editors, In Proceedings of the 12th Annual European Symposium on Algorithms, pages 472-483, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg. Google Scholar
  28. M Luby. A simple parallel algorithm for the maximal independent set problem. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, STOC '85, pages 1-10, New York, NY, USA, 1985. ACM. Google Scholar
  29. 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 Proceedings of the Thirty-second Annual ACM Symposium on Theory of Computing, STOC '00, pages 351-357, New York, NY, USA, 2000. ACM. Google Scholar
  30. Gary L. Miller. Finding small simple cycle separators for 2-connected planar graphs. Journal of Computer and System Sciences, 32(3):265-279, 1986. Google Scholar
  31. Gary L. Miller and Joseph (Seffi) Naor. Flow in planar graphs with multiple sources and sinks. SIAM Journal on Computing, 24(5):1002-1017, 1995. Google Scholar
  32. Gary L. Miller and John H. Reif. Parallel tree contraction part 1: Fundamentals. In Silvio Micali, editor, Randomness and Computation, pages 47-72. JAI Press, Greenwich, Connecticut, 1989. Vol. 5. Google Scholar
  33. K. Mulmuley, U.V. Vazirani, and V.V. Vazirani. Matching is as easy as matrix inversion. In Proceedings of the nineteenth annual ACM conference on Theory of computing, STOC '87, pages 345-354. ACM Press, 1987. Google Scholar
  34. Piotr Sankowski. Faster dynamic matchings and vertex connectivity. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '07, pages 118-126, Philadelphia, PA, USA, 2007. Society for Industrial and Applied Mathematics. Google Scholar
  35. Piotr Sankowski. Processor Efficient Parallel Matching. Theory of Computing Systems, 42(1):73-90, Jan 2008. Google Scholar
  36. Piotr Sankowski. Planar perfect matching is in NC, 2017. URL: http://arxiv.org/abs/arXiv:1709.07869.
  37. Y. Shiloach and Uzi Vishkin. An O(log n) parallel connectivity algorithm. Journal of Algorithms, 3:57-67, 1982. Google Scholar
  38. Ola Svensson and Jakub Tarnawski. The Matching Problem in General Graphs Is in Quasi-NC. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS '17, pages 696-707. IEEE Computer Society, 2017. Google Scholar
  39. R. E. Tarjan and U. Vishkin. Finding biconnected componemts and computing tree functions in logarithmic parallel time. In Proceedings of the 25th Annual IEEE Symposium on Foundations of Computer Science, FOCS '84, pages 12-20, Oct 1984. Google Scholar
  40. Raghunath Tewari and N. V. Vinodchandran. Green’s theorem and isolation in planar graphs. Inf. Comput., 215:1-7, 2012. Google Scholar
  41. Vijay V. Vazirani. Nc algorithms for computing the number of perfect matchings in K_3,3-free graphs and related problems. Information and Computation, 80(2):152-164, 1989. 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