An instance of the maximum weight strongly stable matching problem with incomplete lists and ties is an undirected bipartite graph G = (A cup B, E), with an adjacency list being a linearly ordered list of ties, which are vertices equally good for a given vertex. We are also given a weight function w on the set E. An edge (x, y) in E setminus M is a blocking edge for M if by getting matched to each other neither of the vertices x and y would become worse off and at least one of them would become better off. A matching is strongly stable if there is no blocking edge with respect to it. The goal is to compute a strongly stable matching of maximum weight with respect to w. We give a polyhedral characterisation of the problem and prove that the strongly stable matching polytope is integral. This result implies that the maximum weight strongly stable matching problem can be solved in polynomial time. Thereby answering an open question by Gusfield and Irving [Dan Gusfield and Robert W. Irving, 1989]. The main result of this paper is an efficient O(nm log{(Wn)}) time algorithm for computing a maximum weight strongly stable matching, where we denote n = |V|, m = |E| and W is a maximum weight of an edge in G. For small edge weights we show that the problem can be solved in O(nm) time. Note that the fastest known algorithm for the unweighted version of the problem has O(nm) runtime [Telikepalli Kavitha et al., 2007]. Our algorithm is based on the rotation structure which was constructed for strongly stable matchings in [Adam Kunysz et al., 2016].

An instance of the strongly stable roommates problem with incomplete lists and ties (SRTI) is an undirected non-bipartite graph G = (V,E), with an adjacency list being a linearly ordered list of ties, which are vertices equally good for a given vertex. Ties are disjoint and may contain one vertex. A matching M is a set of vertex-disjoint edges. An edge {x, y} in E\M is a blocking edge for M if x is either unmatched or strictly prefers y to its current partner in M, and y is either unmatched or strictly prefers x to its current partner in M or is indifferent between them. A matching is strongly stable if there is no blocking edge with respect to it. We present an O(nm) time algorithm for computing a strongly stable matching, where we denote n = |V| and m = |E|. The best previously known solution had running time O(m^2) [Scott, 2005]. We also give a characterisation of the set of all strongly stable matchings. We show that there exists a partial order with O(m) elements representing the set of all strongly stable matchings, and we give an O(nm) algorithm for constructing such a representation. Our algorithms are based on a simple reduction to the bipartite version of the problem.

An instance of a strongly stable matching problem (SSMP) is an undirected bipartite graph G = (A ∪ B, E), with an adjacency list of each vertex being a linearly ordered list of ties, which are subsets of vertices equally good for a given vertex. Ties are disjoint and may contain one vertex. A matching M is a set of vertex-disjoint edges. An edge (x, y) ∊ E\M is a blocking edge for M if x is either unmatched or strictly prefers y to its current partner in M, and y is either unmatched or strictly prefers x to its current partner in M or is indifferent between them. A matching is strongly stable if there is no blocking edge with respect to it. We present a characterisation of the set of all strongly stable matchings, thus solving an open problem already stated in the book by Gusfield and Irving [7]. It has previously been shown that strongly stable matchings form a distributive lattice [8] and although the number of strongly stable matchings can be exponential in the number of vertices, we show that there exists a partial order with O(m) elements representing all strongly stable matchings, where m denotes the number of edges in the graph. We give two algorithms that construct two such representations: one in O(nm2) time and the other in O(nm) time, where n denotes the number of vertices in the graph. Note that the construction of the second representation has the same time complexity as that of computing a single strongly stable matching.