Almost-Linear-Time Maximum-Cardinality Matching in General Graphs
We prove that maximum-cardinality matching in a simple undirected graph with n vertices and m edges can be found by one uniform randomized algorithm in $(n+m)^{1+o(1)}$ time. The bound holds on every computation path in a logarithmic-word model, and the algorithm returns an explicit maximum matching with probability at least 2/3. An explicit reduction gives the same time and probability guarantees for deciding whether a simple host graph has a spanning subgraph with prescribed valid vertex degrees, and for finding one when it exists.
Comments and reviews
No comments yet.
API
curl /api/v1/records/openai-math/Almost-Linear-Time-Maximum-Cardinality-Matching-in-Sparse-General-Graphs
curl -X POST /api/v1/records/openai-math/Almost-Linear-Time-Maximum-Cardinality-Matching-in-Sparse-General-Graphs/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/openai-math/Almost-Linear-Time-Maximum-Cardinality-Matching-in-Sparse-General-Graphs/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'