1
$\begingroup$

I have 2 different but similar problems, one belongs to NP and one to L and I don't understand why.

First problem: Input: an undirected graph G with n^2 vertices. Question: Is there exist in G a matching of size n AND an independent set of size n?

Second problem: Input: an undirected graph G with n^2 vertices. Question: Is there exist in G a matching of size n OR an independent set of size n?

The AND problem is in NP and the OR problem is in L. Can someone explain why? Thanks.

Improve this question
$\endgroup$
1
  • $\begingroup$ What have you tried? Where did you get stuck? We want to help you with your specific problems, but as it is we don't know what this problem is and thus how to help. See here for a relevant discussion. We expect you to make a significant effort before asking and to show us what you've tried. $\endgroup$
    – D.W. ♦
    Commented Jan 23, 2015 at 17:17

1 Answer 1

Reset to default
1
$\begingroup$

Note that both problems are in NP. It's just that the first is also NP-hard, and the second is also in L.

Hint for the first problem: Prove that it's NP-hard by reduction from independent set. Given a graph $G=(V,E)$ and a parameter $k \leq |V|$, add an independent set of size $|V|-k$ and a clique of size $|V|^2-|V| \geq 2|V|$ (the case $|V| < 3$ has to be handled separately), and connect all vertices of the clique to all other vertices.

Hint for the second problem: Suppose that $G$ doesn't have an independent set of size $n$. Show that it has a matching of size $n$ by dividing the $n^2$ vertices into $n$ sets of $n$ vertices, and picking an edge from each.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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