Hi all, in which sense is the algorithm in graph_tool.topology.max_cardinality_matching with the heuristic=True switch a heuristic and not exact? As I understand, it might not return a maximum-cardinality matching even if there is one. But what about the edge weights? Does it always return a minimum-weight matching (respectively maximum-weight with minimize=False)? Or is this not guaranteed? Note that there are pitfalls to this question: eg. if all edge weights are equal to one, then the optimal min-weight matching is empty if I do not insist on max-cardinality. Can someone enlighten me what the heuristic actually optimizes? Cardinality or weights? Both (in which sense) or none (what's it good for, then)? And does it always find the optimum for one of those two criteria? Best, Daniel -- Daniel Müllner Stanford University Department of Mathematics 450 Serra Mall, Building 380 Stanford, CA 94305 USA e-mail: muellner@math.stanford.edu http://math.stanford.edu/~muellner