0
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ What have you tried? Where did you get stuck? $\endgroup$ – dkaeae Dec 3 '18 at 7:14
  • $\begingroup$ There are polynomial time algorithms for finding the maximum matching in a graph. $\endgroup$ – Yuval Filmus Dec 3 '18 at 9:19
  • $\begingroup$ 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 $\endgroup$ – CHETAN RAJPUT Dec 3 '18 at 11:03
  • 1
    $\begingroup$ On CS stack exchange, you can certainly assume that people know what P, NP and perfect matchings are. $\endgroup$ – David Richerby Dec 3 '18 at 12:53
1
$\begingroup$

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

You answer this kind of question by searching for algorithms that solve your problem as efficiently as possible and, if there don't seem to be any, searching for NP-completeness results. If you don't find either, then you need to come up with your own algorithm or your own hardness proof.

$\endgroup$
  • $\begingroup$ okay got it. Thanx., Just need to ckear something... Number of graphs are unbounded then can you give argument that finding the matching set is decidable ? $\endgroup$ – CHETAN RAJPUT Dec 3 '18 at 14:27
  • $\begingroup$ p.s : I dont know what i asked is valid or not but still you can flash some light on it. $\endgroup$ – CHETAN RAJPUT Dec 3 '18 at 14:30
  • $\begingroup$ The algorithm takes any graph, of any size, as input and tells you whether or not it has a perfect matching. Any interesting algorithm at all will work for inputs of any size. $\endgroup$ – David Richerby Dec 3 '18 at 16:47

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.