2
$\begingroup$

I have some difficulties in understanding how to prove when a language is in P or is NP-Complete. Specifically, consider the following decision problems w.r.t undirected graphs $G = (V, E)$:

  1. $L_1 = \{ \langle G = (V, E), k\rangle \mid \text{$G$ consists of connected} \\ \text{components of size at most $\log|V|$ each, and has a vertex cover of size $k$}\}$

  2. $L_2 = \{\langle G = (V, E), k \rangle \mid \text{$G$ consists of two connected} \\ \text{ components of size $\frac{|V|}{2}$ each, and has a vertex cover of size $k$} \}$

I think that $L_1$ is in $\text{P}$, and $L_2$ is in $\text{NP-complete}$. Am I right? How can I prove that?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

The language $L_1$ is in P since you can brute force an optimal vertex cover in each connected component.

The language $L_2$ is NP-hard by reduction from vertex cover. Roughly, given an arbitrary graph, we have to make it connected and to add another connected component, controlling the change of the minimum vertex cover throughout the process.

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.