Perfect matching in a graph is a set of edges where any pair does not share a common vertex and every vertex of the graph is the endpoint of an edge from that set. From the paper’s introduction: “A polyomino graph is a connected finite subgraph of the infinite plane grid such that each finite face is surrounded by a regular square of side length 1 (called a cell) and each edge belongs to at least one cell.” It has been an open problem whether finding a perfect matching of a polyomino can be done using an algorithm that runs in linear time in the number of vertices, and this paper offers a solution.

Vertices of the polyomino can be given two colors, white and black, such that every edge connects vertices of different colors. For a subgraph of the polyomino, a difference metric can be defined as the absolute difference in the numbers of white and black vertices of that subgraph. Based on Hall’s theorem, that difference must be zero for a perfect matching to exist.

A key observation used in the paper is that the number of elements in the intersection of a diagonal edge cut with any perfect matching of the graph must equal the difference metric of that diagonal edge cut.

Based on this, and using a labeling scheme of the vertices, the authors have come up with an algorithm that proceeds by considering the diagonal edge cuts near the bottom left corner and using the difference metric to either eliminate forbidden edges or to determine edges that belong to a perfect matching under construction.

In either case, the computation proceeds to the next step on subgraphs formed by that edge cut, eventually terminating with a result that either finds a perfect matching or shows its nonexistence. The authors conclude with a claim that the algorithm is linear because the construction follows a linear process.

Overall, the paper is well written, easy to follow, presents innovative ideas, and contributes an efficient algorithm to this open problem. It will be of much interest to students, researchers, and practitioners.