MHB Ice Cream : NP-complete problem

[mathmari]

Hey!

An ice cream shop has $m$ kinds of ice creams $s_1, \dots , s_m$. On the card there are $n$ cups $b_1, \dots , b_n$. Each cup contains some of the ice cream kinds. The budget of Gina suffices for $k$ cups. Gina wants to choose $k$ cups so that each of the $m$ ice cream kinds are occured. I want to show that Gina has a NP-complete problem.
I have to use reduction of Vertex Cover.

The Vertex Cover problem asks if for a graph $G= (V, E)$ and a $k$ there is a subset $C\subseteq V$ such that for each edge $(u,v)\in E$ it holds that $u\in C$ or $v\in C$.

To reduce the Vertex Cover to the above problem do we see the vertices as the cups and the edges as the ice cream kinds? (Wondering)

 

[Evgeny.Makarov]

An ice cream shop has $m$ kinds of ice creams $s_1, \dots , s_m$. On the card there are $n$ cups $b_1, \dots , b_n$.

What card?

Each cup contains some of the ice cream kinds.

So a cup may contain several ice cream kinds (flavors)?

I am not sure I understand the description.

 

[mathmari]

What card?

So a cup may contain several ice cream kinds (flavors)?

I am not sure I understand the description.

Yes, with kinds I mean flavors and with card I mean the menu. (Blush)

So, it is as follows:
An ice cream shop has $m$ flavors of ice creams $s_1, \dots , s_m$. On the menu there are $n$ cups $b_1, \dots , b_n$. Each cup contains several ice cream flavors. The budget of Gina suffices for $k$ cups. Gina wants to choose $k$ cups so that each of the $m$ ice cream flavors exists. I want to show that Gina has a NP-complete problem.

 

[Evgeny.Makarov]

To reduce the Vertex Cover to the above problem do we see the vertices as the cups and the edges as the ice cream kinds?

Yes.

 

[mathmari]

Is the whole proof the following?

First of all, we have to show that the problem is in NP. A non-deterministic Turing Machine guesses $k$ cups and then it checks if each of the $m$ ice cream flavors exists. The Turing Machine needs polynomial time for that, and especially time $m$.

Then to show that the problem is NP-hard we reduce the Vertex Cover Problem to the above one.
We see the vertices as the cups and the edges as the ice cream flavors. Therefore, there is a subset $B$ of the set of the cups such that for each flavor $s_i$ it holds that $s_i\in B$ iff there is a subset $C\subseteq V$ such that for each edge $(u,v)\in E$ it holds that $u\in C$ or $v\in C$.
That means that the above problem has a solution iff the Vertex Cover Problem has a solution.
Since there is no algorithm that solves the Vertex Cover Problem in polynomial time, i.e. the Vertex Cover Problem is NP-complete, we conclude that the ice cream problem is also NP-complete.

Is everything correct? Could I improve something? (Wondering)

 

[Evgeny.Makarov]

First of all, we have to show that the problem is in NP. A non-deterministic Turing Machine guesses $k$ cups and then it checks if each of the $m$ ice cream flavors exists.

Better: "...checks if they contain all $m$ flavors".

The Turing Machine needs polynomial time for that, and especially time $m$.

It's unlikely the time is precisely $m$.

Then to show that the problem is NP-hard we reduce the Vertex Cover Problem to the above one.
We see the vertices as the cups and the edges as the ice cream flavors. Therefore, there is a subset $B$ of the set of the cups such that for each flavor $s_i$ it holds that $s_i\in B$ iff ...

$B$ is a set of vertices and $s_i$ is an edge. It's a type error to say that $s_i\in B$.

there is a subset $C\subseteq V$ such that for each edge $(u,v)\in E$ it holds that $u\in C$ or $v\in C$.

This is the first time $V$ and $E$ are used.

Since there is no algorithm that solves the Vertex Cover Problem in polynomial time

This conjecture is still unproved.

 

[mathmari]

First of all, we have to show that the problem is in NP. A non-deterministic Turing Machine guesses $k$ cups and then it checks if they contain all $m$ flavors. The Turing Machine needs polynomial time for that.
Why is the time not $m$ ? (Wondering)

Then to show that the problem is NP-hard we reduce the Vertex Cover Problem to the above one.
We see the vertices as the cups and the edges as the ice cream flavors.
Therefore, there is a subset $B$ of the set of the cups such that each flavor $s_i$ is in one cup of $B$ iff there is a subset of the set of vertices $C\subseteq V$ such that for each edge $(u,v)\in E$, where $E$ the set of edges, it holds that $u\in C$ or $v\in C$.
That means that the above problem has a solution iff the Vertex Cover Problem has a solution.
Since there is no algorithm that solves the Vertex Cover Problem in polynomial time, i.e. the Vertex Cover Problem is NP-complete, we conclude that the ice cream problem is also NP-complete.

This conjecture is still unproved.

What do you mean? (Wondering)