Document Open Access Logo

A Scaling Algorithm for Weighted f-Factors in General Graphs

Authors Ran Duan, Haoqing He, Tianyi Zhang

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.41.pdf
  • Filesize: 0.62 MB
  • 17 pages

Document Identifiers

Author Details

Ran Duan
  • Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, China
Haoqing He
  • Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, China
Tianyi Zhang
  • Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, China

Cite As Get BibTex

Ran Duan, Haoqing He, and Tianyi Zhang. A Scaling Algorithm for Weighted f-Factors in General Graphs. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 41:1-41:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ICALP.2020.41

Abstract

We study the maximum weight perfect f-factor problem on any general simple graph G = (V,E,ω) with positive integral edge weights w, and n = |V|, m = |E|. When we have a function f:V → ℕ_+ on vertices, a perfect f-factor is a generalized matching so that every vertex u is matched to exactly f(u) different edges. The previous best results on this problem have running time O(m f(V)) [Gabow 2018] or Õ(W(f(V))^2.373)) [Gabow and Sankowski 2013], where W is the maximum edge weight, and f(V) = ∑_{u ∈ V}f(u). In this paper, we present a scaling algorithm for this problem with running time Õ(mn^{2/3} log W). Previously this bound is only known for bipartite graphs [Gabow and Tarjan 1989]. The advantage is that the running time is independent of f(V), and consequently it breaks the Ω(mn) barrier for large f(V) even for the unweighted f-factor problem in general graphs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Scaling Algorithm
  • f-Factors
  • General Graphs

Metrics

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

Related Versions

References

  1. Michael B Cohen, Aleksander Madry, Piotr Sankowski, and Adrian Vladu. Negative-weight shortest paths and unit capacity minimum cost flow in Õ(m^10/7log w). In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 752-771. SIAM, 2017. Google Scholar
  2. Ran Duan and Seth Pettie. Linear-time approximation for maximum weight matching. Journal of the ACM (JACM), 61(1):1, 2014. Google Scholar
  3. Ran Duan, Seth Pettie, and Hsin-Hao Su. Scaling algorithms for weighted matching in general graphs. ACM Transactions on Algorithms (TALG), 14(1):8, 2018. Google Scholar
  4. Jack Edmonds and Richard M Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM (JACM), 19(2):248-264, 1972. Google Scholar
  5. Shimon Even and R Endre Tarjan. Network flow and testing graph connectivity. SIAM journal on computing, 4(4):507-518, 1975. Google Scholar
  6. 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, pages 448-456. ACM, 1983. Google Scholar
  7. Harold N Gabow. Scaling algorithms for network problems. In 24th Annual Symposium on Foundations of Computer Science (SFCS 1983), pages 248-258. IEEE, 1983. Google Scholar
  8. Harold N Gabow. Data structures for weighted matching and extensions to b-matching and f-factors. ACM Transactions on Algorithms (TALG), 14(3):39, 2018. Google Scholar
  9. Harold N Gabow and Piotr Sankowski. Algebraic algorithms for b-matching, shortest undirected paths, and f-factors. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 137-146. IEEE, 2013. Google Scholar
  10. Harold N Gabow and Robert E Tarjan. Faster scaling algorithms for network problems. SIAM Journal on Computing, 18(5):1013-1036, 1989. Google Scholar
  11. Andrew Goldberg and Robert Tarjan. Solving minimum-cost flow problems by successive approximation. In Proceedings of the nineteenth annual ACM symposium on Theory of computing, pages 7-18. ACM, 1987. Google Scholar
  12. Andrew V Goldberg and Satish Rao. Beyond the flow decomposition barrier. Journal of the ACM (JACM), 45(5):783-797, 1998. Google Scholar
  13. Dawei Huang and Seth Pettie. Approximate generalized matching: f-factors and f-edge covers. arXiv preprint, 2017. URL: http://arxiv.org/abs/1706.05761.
  14. Alexander V Karzanov. On finding maximum flows in networks with special structure and some applications. Matematicheskie Voprosy Upravleniya Proizvodstvom, 5:81-94, 1973. Google Scholar
  15. Yin Tat Lee and Aaron Sidford. Path finding methods for linear programming: Solving linear programs in Õ(√rank) iterations and faster algorithms for maximum flow. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 424-433. IEEE, 2014. Google Scholar
  16. A. Schrijver. Combinatorial Optimization - Polyhedra and Efficiency. Springer, 2003. 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 About DROPS Imprint Privacy Contact