SPOILER ALERT : If you didn't solve the problems in NEERC and you want to enjoy the problems, please don't read.
It looks there are few problems about general graph matching in the community. And there are a few teams who solved problem B in NEERC both online and onsite. However, the reduction from maximum cost perfection matching to this problem is simple to me. So I want to share some problems for practice.
You can find the template here and here.
The shortest code of the maximum cost matching problem is about 5.7k.
There is a simple way to find the cardinality of the maximum matching, which is half of the rank of the Tutte matrix. We can use Gaussian elimination to compute the rank of a matrix. By the way, if the maximum cost is no more than W, we can also find the maximum cost matching by Tutte matrix and polynomial interpolation in O(Wn3). It is easier to implement.
Here is a collection of general graph matching problems. I'm too lazy to write solutions to these problems. And I can't remember the solution to some problems clearly. You can discuss the problems here.
Chinese postman problem. Find a shortest closed path or circuit that visits every edge of a (connected) undirected graph.
Given an undirected weighted graph G, find a minimum weight subset E such that each vertex is incident on at least one edges in E.
Min cost cycle cover. A cycle cover of an undirected graph is a collection of vertex-disjoint cycles such that each vertex belongs to exactly one cycle. We require each cycle contains at least three vertices. In a weighted graph, the weight of a cycle cover is the sum of the weights of all its edges. Find the minimum total weight cycle cover.
Given an undirected positive weighted graph G, find the shortest simple path from s to t with even edges.
A problem from winter camp 2016 There are n balls and m baskets. There are e relationships such that ball u can be put into basket v. We can put at most 3 balls in each basket. And we want to put every ball into baskets. We want to maximize the number of baskets with at most 1 ball.
A problem from Chinese Team Test 2013 Find the maximum cut of an undirected planar graph. You need to partition the vertices into two sets S, T. Maximize
.Two matching. Given an undirected weighted graph G, find a minimum weight subset E such that the degree of each vertex in the subset E is no more than 2.
Undirected Vertex Geography. Alice and Bob are playing a game on an undirected graph. They move the token to the unvisited neighbor alternatively. The player who can't move loses. Determine the winner of each starting point. Algebra makes your life much easier in this problem.
Given a DAG. You can remove at most 2 vertices with zero in degree in each round. How many rounds do you need to remove all the vertices?
