Stable matchings and kernels
Contents
Problems in this category
- Cyclic stable matchings
- Deciding kernel-perfectness
- Deciding the existence of popular matchings
- Existence of completely stable flow
- Finding a 2-way stable 3-way exchange
- Finding kernels in special digraphs
- Finding the largest popular matching in a bipartite graph
- Tidbits/Kernel-perfectness
- List colouring of two matroids
- Maximum weakly stable matchings in graphs without odd preference cycles
- Orientation-compatible w-vertex cover
- Polyhedral description of kernels
- Quasi-kernels and quasi-sinks
- Small quasi-kernels in directed graphs
Introduction
From the viewpoint of combinatorial optimization, stable matching problems are interesting because there are many beautiful algorithmic and structural results, yet these do not seem to fit into the usual framework of flows and matchings. The field is quite active and generalizations have been achieved in several directions, but a unified understanding of the results is still missing.
One general approach to explain results on the existence of stable matchings is to derive them from fixed point theorems, see the survey of Fleiner [1]. However, no polynomial algorithms are known for these fixed point theorems in general, so this approach does not explain the algorithmic results. Indeed, it would be crucial to understand what properties make these particular fixed point problems polynomially solvable.
An interesting open problem where fixed point methods have not been successful yet is the question on cyclic stable matchings, where triplets are considered instead of pairs. There are many other extensions and modifications of the stable matching problem that lead to interesting questions; in the following we mention some of them.
Related concepts
Stable flows
The notion of stable flow has recently been introduced by Fleiner [2] as a natural generalization of the stable marriage problem, just as network flows generalize bipartite matching. There are probably many interesting questions that can be asked about them, here we mention one about the existence of completely stable flow:
|
Is there a polynomial algorithm that decides whether a network with preferences has a completely stable flow? |
Popular matchings
A possible modification of the stable matching problem is that we require some kind of global (majority) stability instead of local stability. This is captured in the notion of popular matching. Every stable matching is popular, but not vice versa. The problem of Finding the largest popular matching in a bipartite graph has been solved, but the complexity of Deciding the existence of popular matchings is still open for non-bipartite graphs. It seems that the standard methods of matching theory are more useful in popular matching problems than in stable matching problems.
Kernels
Another way to look at stable matchings is that they are kernels in specially oriented line graphs. This view offers natural generalizations of stable matching problems, if we allow different kinds of orientations, or we do not restrict ourselves to line graphs.
Very few cases are known apart from stable matchings (and some simple cases) where kernels can be found in polynomial time - see the open problems Finding kernels in special digraphs and Deciding kernel-perfectness, and also the blog post Blog:Tidbits/Kernel-perfectness. Even less is known about the Polyhedral description of kernels - which is not surprising, given that the problem of finding a minimum weight kernel is considerably more difficult than finding a kernel.
While it may be hard to decide if there is a kernel, a quasi-kernel always exist and it is easy to find. However, it is open whether we can always find one that is not too large.
Other directions
Approximation algorithms
In preference systems with ties, several stable matching problems become NP-hard, so good approximation algorithms are of primary importance. A breakthrough by Király [3] has been a simple 5/3-approximation algorithm for the maximum stable marriage problem, and a 3/2-approximation algorithm if only one side has ties. The former has been improved to a (more complicated) 3/2-approximation algorithm by McDermid [4], followed by linear time 3/2-approximation algorithms by Paluch [5] and Király [6].
In the non-bipartite case, it is NP-complete to decide the existence of a weakly stable matching, so approximating the maximum size weakly stable matching is impossible. However, one can ask for approximating Maximum weakly stable matchings in graphs without odd preference cycles.
List colouring
An outstanding open problem in graph theory is the Edge list colouring conjecture (see the Open Problem Garden). Its relation to stable matchings is that Galvin [7] proved the conjecture for bipartite multigraphs usig the stable marriage theorem. The question List colouring of two matroids asks whether Galvin's result can be extended to other classes of matroids.
References
- ↑ T. Fleiner, Some results on stable matchings and fixed points, EGRES Technical Report no. 2002-08.
- ↑ T. Fleiner, On stable matchings and flows, DOI link, preliminary EGRES report.
- ↑ Z. Király, Better and Simpler Approximation Algorithms for the Stable Marriage Problem, Proc. ESA2008, Lecture Notes in Computer Science 5193 (2008), 623-634. DOI link, EGRES Technical Report.
- ↑ E. McDermid, A 3/2-Approximation Algorithm for General Stable Marriage, Proc. ICALP2009, Lecture Notes in Computer Science 5555 (2009), 689-700. DOI link. Author link.
- ↑ K. Paluch, Faster and simpler approximation of stable matchings, arXiv link.
- ↑ Z. Király, Approximation of maximum stable marriage, EGRES Technical Report.
- ↑ F. Galvin, The list chromatic index of a bipartite multigraph, Journal of Combinatorial Theory Series B 63 (1995), 153-158. DOI link.
