[問題案]Matching on Bipartite Graph(bipartitematching)

[yosupo06]

No description provided.

[yosupo06]

自分の提出 2678, 2679, 2680 が Library Checker では AC となっていますが、他の問題で落ちたので多分ライブラリとして間違っています。

との報告がきた　ランダムだけだと弱いよね…(トホホ)

[yosupo06]

https://judge.yosupo.jp/submission/3463 いろいろミスってるのに通った

[yosupo06]

最悪ケースがよくわからなかったが、https://codeforces.com/blog/entry/58048 ここに情報がまとまっていそう

[maspypy]

テストケース追加済っぽいので、 close

[rpeng233]

Would it be possible to increase the limits to the same sizes as the bipartite ones? (V <= 10e5, E <= 2e5?). The current fastest runtimes are all 1ms, and the theoretical best running times of general graph matchings seem to be the same as the bipartite case?

[maspypy]

Basically, we don't change the constraints once the problem is published. However, we may add a hard version of a problem if necessary.

---

The current fastest runtimes are all 1ms, and the theoretical best running times of general graph matchings seem to be the same as the bipartite case?

Many solutions solve:

• Bipartite matching in $\Theta(m\sqrt{n})$ time, and
• General matching in $\Theta(n^3)$ or $\Theta(nm\polylog(n,m))$, etc.

Consequently, it seems hard to solve general matching within the same constraints.

[rpeng233]

General matching also has some m\sqrt{n} time algorithms that seem implementable: https://arxiv.org/abs/2012.03582, https://dl.acm.org/doi/pdf/10.1145/115234.115366

Agree that it's a much harder problem though. Not clear if such variants will ever show up on CP.... I was just looking for a place where such implementations can be benchmarked.

[maspypy]

Thank you.
It is possible to add the problem to Library Checker regardless of whether they are included in competitive programming questions. However, preparing the answers might be difficult. Would it be possible for you to provide them if you have the appropriate implementation?

[rpeng233]

My (likely false) impression from the bipartite case is that 'just' augmenting paths with some randomized tie breaking does fine, so I feel if it's a 5s limit, running a slower code for 5 minutes be more than sufficient to generate data.

There are all sorts of generators from http://archive.dimacs.rutgers.edu/pub/netflow/instances/matching/ as well. So I should be able to put together and maintain a data set.

[maspypy]

I said about the implementation of the solution.

[rpeng233]

I think https://judge.yosupo.jp/submission/51989 is a linear memory solution, so it should just work for 10^5 edges.

My guess is constructing data to make this (plus some greedy initializations) is already a major challenge.

I have heard of people with m^{1.5} implementations (e.g. https://tmt514.github.io/ has written papers on this). Let me ask around ...