Efficient Kernelization Algorithm for Bipartite Graph Matching
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929609559244800 |
|---|---|
| author | Wu, Guang Gan, Xinbiao Pang, Zhengbin Huang, Bo Ran, Bopin |
| author_facet | Wu, Guang Gan, Xinbiao Pang, Zhengbin Huang, Bo Ran, Bopin |
| contents | Finding the maximum matching in bipartite graphs is a fundamental graph operation widely used in various fields. To expedite the acquisition of the maximum matching, Karp and Sipser introduced two data reduction rules aimed at decreasing the input size. However, the KaSi algorithm, which implements the two data reduction rules, has several drawbacks: a high upper bound on time complexity and inefficient storage structure. The poor upper bound on time complexity makes the algorithm lack robustness when dealing with extreme cases, and the inefficient storage structure struggles to balance vertex merging and neighborhood traversal operations, leading to poor performance on real-life graphs. To address these issues, we introduced MVM, an algorithm incorporating three novel optimization strategies to implement the data reduction rules. Our theoretical analysis proves that the MVM algorithm, even when using data structures with the worst search efficiency, can still maintain near-linear time complexity, ensuring the algorithm's robustness. Additionally, we designed an innovative storage format that supports efficient vertex merging operations while preserving the locality of edge sets, thus ensuring the efficiency of neighborhood traversals in graph algorithms. Finally, we conduct evaluations on both real-life and synthetic graphs. Extensive experiments demonstrate the superiority of our method. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_00704 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Efficient Kernelization Algorithm for Bipartite Graph Matching Wu, Guang Gan, Xinbiao Pang, Zhengbin Huang, Bo Ran, Bopin Data Structures and Algorithms Finding the maximum matching in bipartite graphs is a fundamental graph operation widely used in various fields. To expedite the acquisition of the maximum matching, Karp and Sipser introduced two data reduction rules aimed at decreasing the input size. However, the KaSi algorithm, which implements the two data reduction rules, has several drawbacks: a high upper bound on time complexity and inefficient storage structure. The poor upper bound on time complexity makes the algorithm lack robustness when dealing with extreme cases, and the inefficient storage structure struggles to balance vertex merging and neighborhood traversal operations, leading to poor performance on real-life graphs. To address these issues, we introduced MVM, an algorithm incorporating three novel optimization strategies to implement the data reduction rules. Our theoretical analysis proves that the MVM algorithm, even when using data structures with the worst search efficiency, can still maintain near-linear time complexity, ensuring the algorithm's robustness. Additionally, we designed an innovative storage format that supports efficient vertex merging operations while preserving the locality of edge sets, thus ensuring the efficiency of neighborhood traversals in graph algorithms. Finally, we conduct evaluations on both real-life and synthetic graphs. Extensive experiments demonstrate the superiority of our method. |
| title | Efficient Kernelization Algorithm for Bipartite Graph Matching |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2412.00704 |