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

<blockquote>
  <p>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? </p>
</blockquote>

CC BY-SA 3.0
2014-10-09T17:59:24.453Z
The best known lower bound is NL-hardness.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-10-13T03:53:55.037Z
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.)
Tsuyoshi Ito
CC BY-SA 3.0
2014-10-21T04:12:03.447Z
If you're just given the _adjacency matrix_, known results related to the [AKR conjecture](http://en.wikipedia.org/wiki/Aanderaa%E2%80%93Karp%E2%80%93Rosenberg_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.
Neal Young
<cc.complexity-theory><ds.algorithms><reference-request><graph-theory><matching>
Is it possible to solve perfect matching in linear time
juna
# Is it possible to solve perfect matching in linear time

(Asked by: username_0 on 2014-10-09)

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?

**Tags:** cc.complexity-theory, ds.algorithms, reference-request, graph-theory, matching

> **Comments:**
> **username_1**: The best known lower bound is NL-hardness.  
> **username_2**: 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.)  
> **username_3**: If you're just given the _adjacency matrix_, known results related to the [AKR conjecture](http://en.wikipedia.org/wiki/Aanderaa%E2%80%93Karp%E2%80%93Rosenberg_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.  

---

## 0 answers

