Decision Vertex Cover

# Minimum Vertex Cover Decision (Small Graph) ## Problem Statement Given an undirected graph $G = (V, E)$ with $n$ vertices and $m$ edges, and an integer $k$, determine if there exists a vertex cover of size at most $k$. A *vertex cover* of a graph $G$ is a subset of its vertices $V' \subseteq V$ such that for every edge $(u, v) \in E$, at least one of its endpoints (either $u$ or $v$) is in $V'$. In simpler terms, a vertex cover is a set of vertices such that every edge in the graph is incident to at least one vertex in the set. Your task is to output "YES" if a vertex cover of size at most $k$ exists, and "NO" otherwise. ## Input Format - The first line contains three integers $n$, $m$, and $k$ ($1 \le n \le 20$, $0 \le m \le \frac{n(n-1)}{2}$, $0 \le k \le n$). Here, $n$ is the number of vertices, $m$ is the number of edges, and $k$ is the maximum allowed size for the vertex cover. - Each of the next $m$ lines contains two integers $u$ and $v$ ($1 \le u, v \le n$, $u \ne v$), representing an undirected edge between vertex $u$ and vertex $v$. The graph is guaranteed to be simple (no self-loops, no multiple edges between the same pair of vertices). ## Output Format - Output "YES" if there exists a vertex cover of size at most $k$, and "NO" otherwise. ## Sample Test Cases ### Sample Input 1 ``` 3 3 2 1 2 2 3 3 1 ``` ### Sample Output 1 ``` YES ``` ### Sample Input 2 ``` 4 2 1 1 2 3 4 ``` ### Sample Output 2 ``` NO ``` ## Constraints - $1 \le n \le 20$ - $0 \le m \le n(n-1)/2$ - $0 \le k \le n$ - $1 \le u, v \le n$ - $u \ne v$ - Time limit: 1 second - Memory limit: 256 MB ## Explanation For Sample Input 1: The graph has $n=3$ vertices and $m=3$ edges, forming a triangle: $(1,2)$, $(2,3)$, $(3,1)$. We need to determine if a vertex cover of size at most $k=2$ exists. The set of vertices $V' = \{1, 2\}$ is a valid vertex cover of size $2$: it covers edge $(1,2)$ (both $1$ and $2$ are in $V'$), edge $(2,3)$ (since $2 \in V'$), and edge $(3,1)$ (since $1 \in V'$). Since a vertex cover of size $2$ (which is $\le k$) exists, the answer is "YES". For Sample Input 2: The graph has $n=4$ vertices and $m=2$ edges: $(1,2)$ and $(3,4)$. We need to determine if a vertex cover of size at most $k=1$ exists. To cover edge $(1,2)$, we must include either vertex $1$ or vertex $2$ in our vertex cover. Similarly, to cover edge $(3,4)$, we must include either vertex $3$ or vertex $4$. Since these two edges are disjoint, any vertex cover must include at least two vertices (e.g., $\{1, 3\}$ or $\{2, 4\}$). Thus, no vertex cover of size $1$ exists. Since $k=1$, the answer is "NO".