# Can we detect perfect matchings in P? in NP? in coNP?

This question concerns the classes P and N P . If you are familiar with them, you may skip the definitions and go directly to the question. Let L be a set. We say that L is in P if there is some algorithm which given input x decides if x is in L or not in time bounded by a polynomial in the length of x. For example, the set of all connected graphs is in P , because there is an algorithm which, given a graph graph, can decide if it is connected or not in time roughly proportional to the number of edges of the graph.

The class NP is a superset of class P . It contains those sets that have membership witnesses that can be verified in polynomial time. For example, the set of composite numbers is in NP . To see this take the witness for a composite number to be one of its divisors. Then the verification process consists of performing just one division using two reasonable size numbers. Similarly, the set of those graphs that have a Hamilton cycle, i.e. a cycle containing all the vertices of the graph, is in in NP. To verify that the graph has a Hamilton cycle we just check if the witnessing sequence of vertices indeed a cycle of the graph that passes through all the vertices of the graph. This can be done in time that is polynomial in the size of the graph.

More precisely, if L is a set in P consisting of elements of the form (x, w), then the set M={x:∃w,|w|≤|x|k and (x,w)∈L},

is in N P . Let G = (V, E) be a graph. G is said to have perfect matching if there is a subset M of the edges of G so that

No two edges in M intersect (have a vertex in common); and Every vertex of G has an edge in M. Let MATCH be the set of all graphs that have a perfect matching. Let ~MATCH be the set of graphs that do not have a perfect matching. Let o(G) be the number of components of G that have an odd number of vertices.

Tutte’s Theorem: G∈MATCH if and only if for all subsets S of V, the number of components in G − S (the graph formed by deleting the vertices in S) with an odd number of vertices is at most |S|. That is, G∈MATCH↔∀S⊆Vo(G−S)≤|S|. Which of the following is true?

1. MATCH∈NP and ~MATCH ∉ NP
2. ~MATCH ∈NP and MATCH ∉ NP
3. MATCH ∈ NP and ~MATCH ∈NP
4. MATCH ∉ P and ~MATCH ∉ P
5. None of the above

How to approach such type of questions ?

• What have you tried? Where did you get stuck? – dkaeae Dec 3 '18 at 7:14
• There are polynomial time algorithms for finding the maximum matching in a graph. – Yuval Filmus Dec 3 '18 at 9:19
• yes true but MATCH is not for given graph rather it is set of such graphs so i guess we can say using cantor's argument that TM will not exists. And if it true then we can classify this problem in whether P or NP – CHETAN RAJPUT Dec 3 '18 at 11:03
• On CS stack exchange, you can certainly assume that people know what P, NP and perfect matchings are. – David Richerby Dec 3 '18 at 12:53

Edmonds' "blossom algorithm" determines membership in MATCH deterministically in time $$O(|E|\,|V|^2)$$.