recategorized by
1,000 views
7 votes
7 votes

This question concerns the classes $P$ and $NP.$ 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 : \exists w, |w| ≤ |x|^k\text{ and }(x, w) \in 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

  1. No two edges in $M$ intersect (have a vertex in common); and
  2. Every vertex of $G$ has an edge in $M.$

Let $\text{MATCH}$ be the set of all graphs that have a perfect matching. Let $\overline{\text{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.

$\text{Tutte’s Theorem:}$ $G \in \text{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 \in \text{MATCH} ↔ \forall S \subseteq V o(G − S) \leq |S|.$$

Which of the following is true?

  1. $\text{MATCH} ∈ NP\text{ and }\overline{\text{MATCH}} \notin NP$
  2. $\overline{\text{MATCH}} ∈ NP\text{ and }\text{MATCH} \notin NP$
  3. $\text{MATCH} ∈ NP\text{ and }\overline{\text{MATCH}} ∈ NP$
  4. $\text{MATCH} \notin P\text{ and } \overline{\text{MATCH}} \notin P$
  5. none of the above
recategorized by

1 Answer

Best answer
2 votes
2 votes

First of all let us see some things asked in question:

  1. We say $\text{MATCH} \in P$ if given a graph $G$ we can say in polynomial time using a deterministic Turing machine if $G$ has a perfect matching.
  2. We say $\text{MATCH} \in NP$ if given a graph $G$ we can say in polynomial time using a non-deterministic Turing machine if $G$ has a perfect matching.
    1. Equivalently given a subset $M$ of edges of $G$ we can say in polynomial time using a deterministic Turing machine, if it is a perfect matching for $G.$
    2. Similarly, we say $\overline{\text{MATCH}} \in NP$ if given a subset $M$ of edges of $G$ we can say in polynomial time using a deterministic Turing machine, if it is NOT a perfect matching for $G.$

So, we can see if point $2.1$ given above is possible. To do this for the given subset of edges $M$ we have to see

  1. No two edges in $M$ intersect (have a vertex in common); 
    Can be done just by traversing the edges and seeing for common vertex. Naive implementation can be done in $O(V|M|)$ time by marking the two vertices of each edge and see if any vertex gets marked twice which is polynomial.
  2. Every vertex of $G$ has an edge in $M.$ 
    We can do the same procedure done for above and finally see if any vertex is left unmarked. So, polynomial time possible.

If the answer to steps $1$ and $2$ are "Yes", then $M$ is a perfect matching for $G$ and we proved that $\text{MATCH} \in NP.$

If the answer to any one of steps $1$ or $2$ above is "No", then $M$ is not a perfect matching for $G$ and we proved that $\overline{\text{MATCH}} \in NP.$

Thus, both the problems are in $NP.$

Option C is correct.

Further Read: http://mathworld.wolfram.com/PerfectMatching.html 

Answer:

Related questions

4 votes
4 votes
2 answers
2