9
$\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?

Improve this question
$\endgroup$
3
  • $\begingroup$ The best known lower bound is NL-hardness. $\endgroup$
    – Mohammad Al-Turkistany
    Oct 9, 2014 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, 2014 at 3:53
  • 2
    $\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, 2014 at 4:12

0

Reset to default

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.