8
$\begingroup$

As we know matching can be solve in polynomial time. One classical and famous algorithm is designed by Karp and Hopcroft.

Is it possible to solve perfect matching problem in linear time for given $G=(V,E)$? Here, we say linear time as $O(|V|+|E|)$. I think it is impossible to solve it in linear time. Are there plausible evidence such as complexity lower bounds for some limited computation models or conditional results indicating the linear time intractablity of matching problems?

$\endgroup$
  • $\begingroup$ The best known lower bound is NL-hardness. $\endgroup$ – Mohammad Al-Turkistany Oct 9 '14 at 17:59
  • 3
    $\begingroup$ Which computational model are you considering? I think that the computational model matters a lot in lower bounds like this. For example, even the input length cannot be O(|V|+|E|) if we count the number of bits. (It is not that I know a nontrivial lower bound for perfect matching in any computational model.) $\endgroup$ – Tsuyoshi Ito Oct 13 '14 at 3:53
  • 1
    $\begingroup$ If you're just given the adjacency matrix, known results related to the AKR conjecture would imply that you need to check $\Omega(n^2)$ entries in the worst case to verify that $G$ has a perfect matching using any deterministic algorithm. If you allow non-deterministic algorithms, of course you can verify that $G$ has a perfect matching in linear time. So any lower bound of the kind you seek would have to separate deterministic algorithms from non-deterministic ones. $\endgroup$ – Neal Young Oct 21 '14 at 4:12

Your Answer

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

Browse other questions tagged or ask your own question.