Under isolation lemma if you have a graph with $2n$ vertices and $m$ edges an isolating weight assignment can be obtained by assigning edges weights randomly from $\{1,2,\dots,2m-1,2m\}$. A weight assignment is isolating if there is an unique perfect matching with minimum sum weight.

Is $\Omega(m)$ weight necessary or would it be possible that there is a (deterministic) scheme that can get the job done in $O(\sqrt m)$?

Note that the best weights we know uses $O(2^m)$.


A deterministic scheme with tiny weights is easy to achieve: first, compute an arbitrary perfect matching, deterministically. Then, give the matched edges weight zero and all other edges weight one. The difficult question is how to compute a deterministic isolating scheme more quickly than finding a perfect matching.

| cite | improve this answer | |
  • $\begingroup$ Isolation lemma does not work that way (it assigns weights without 'knowing' the matchings). $\endgroup$ – user34945 Mar 21 '16 at 19:23
  • 3
    $\begingroup$ Sure, but you haven't asked your question in a way that prevents it from working that way. $\endgroup$ – David Eppstein Mar 21 '16 at 21:09
  • $\begingroup$ 'Isolating weights' is the short form used in literature for which I have given a one sentence definition. Please feel free to modify the text of the problem and it is clear English is not very precise. $\endgroup$ – user34945 Mar 22 '16 at 19:23
  • $\begingroup$ Well, but there are multiple modifications one could choose. Do you want a set of weights that is chosen independently of the input graph? Do you want them to be chosen using the input graph, but faster than the best sequential matching algorithm? Are you looking for a derandomization of the PRAM algorithm for matching? $\endgroup$ – David Eppstein Mar 22 '16 at 20:32
  • $\begingroup$ Let me think carefully and get back. $\endgroup$ – user34945 Mar 22 '16 at 20:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy