Characterization of Super-stable Matchings
share
An instance of the super-stable matching problem with incomplete lists and ties is an undirected bipartite graph G = (A ∪ B, E), with an adjacency list being a linearly ordered list of ties. Ties are subsets of vertices equally good for a given vertex. An edge (x,y) ∈ E \ M is a blocking edge for a matching M if by getting matched to each other neither of the vertices x and y would become worse off. Thus, there is no disadvantage if the two vertices would like to match up. A matching M is super-stable if there is no blocking edge with respect to M. It has previously been shown that super-stable matchings form a distributive lattice and the number of super-stable matchings can be exponential in the number of vertices. We give two compact representations of size O(m) that can be used to construct all super-stable matchings, where m denotes the number of edges in the graph. The construction of the second representation takes O(mn) time, where n denotes the number of vertices in the graph, and gives an explicit rotation poset similar to the rotation poset in the classical stable marriage problem. We also give a polyhedral characterisation of the set of all super-stable matchings and prove that the super-stable matching polytope is integral, thus solving an open problem stated in the book by Gusfield and Irving .
READ FULL TEXT