2
$\begingroup$

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)$.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Isolation lemma does not work that way (it assigns weights without 'knowing' the matchings). $\endgroup$
    – user34945
    Mar 21, 2016 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, 2016 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, 2016 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, 2016 at 20:32
  • $\begingroup$ Let me think carefully and get back. $\endgroup$
    – user34945
    Mar 22, 2016 at 20:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.