- Combination Optimization: Finding the best combination structure that satisfies certain conditions based on a specific criterion.
- Matching Problem:
- Bipartite Graph Matching:
- Vertex Covering Set: A set of vertices that covers all edges, meaning at least one vertex from each edge is included.
- Theorem: The maximum number of edges in a matching is equal to the minimum number of vertices in a covering set (only in bipartite graphs).
- In other words, to verify a matching with k edges, we can check if it is greater than or equal to max or less than or equal to min.
- To find the matching with the maximum number of edges, we need to search for a covering set with k vertices or a matching with k+1 edges.
- To find a matching with k+1 edges, we search for an “augmenting path” (changing 0-1-0 to 1-0-1).
- General Graph Matching:
- There is a generalized version of the above theorem.
- After selecting vertices, we use the remaining vertices that do not cover them.
- When searching for an augmenting path, if we find an odd-length cycle, it means we can reach any vertex from any other vertex.
- This is called a “blossom”.
- It can be treated as a single vertex.
- By contracting it and finding an augmenting path, we can maximize the number of matchings.
- The algorithmic approach is the same as in bipartite graphs.
- Shortest path search with even-odd constraints can be solved using weighted matching.
- The graph is divided into two layers, and matching is performed.
- There is also a technique that applies blossom contraction in Dijkstra’s algorithm.
- It can find the shortest odd-length path.
- If the start and end are included in a blossom, it is expanded.
- Minimum Spanning Tree Problem and Traveling Salesman Problem are similar.
- However, the former can be solved optimally with a greedy algorithm, while the latter cannot.
- There are problems that are easier to solve and problems that are harder to solve.
- Easier problems: Creating a general framework (Matroids).
- Harder problems: Approximation algorithms or heuristics.
- Sometimes the methods used for easier problems can be applied.
- http://www.kurims.kyoto-u.ac.jp/~kenkyubu/kokai-koza/H22-iwata.pdf
- Matching Problem
- Perfect Matching: Creating a set of pairs using all the vertices.
- Matching problem and Traveling Salesman Problem are similar.
(Information Science Expert)