1
$\begingroup$

I'm preparing for my exam and I got stuck on the following problem:

The gardening problem:

We have access to a set of different types of seeds and a number of plant pots.For each plant pot, there is a limit to how many seeds can be planted in that particular pot.

In addition, there are seeds that cannot be planted in the same pot. These requirements are described by a list of pairs of seeds that do not want to be planted in the same pot. Each seed is featured in at least one pair in the list.

The goal is to plant as many different types of seeds as possible, given the number of seeds that can be planted in each pot and a list of pairs of seeds that can't grow in the same pot.

I am supposed to formulate the gardening problem as a decision problem by introducing a goal K, and then show that this decision problem is NP-complete. I must show that it is included in NP and by designing a polynomial Karp reduction between the NP-complete problem Independent set and the gardening problem.

In order to show that a problem is included in NP I know that I must show that a given solution can be verified in polynomial time (this doesn't seem too difficult). It's the Karp reduction I'm a bit unsure how to do and need help with. I get confused by the different capacities of the pots.

My solution so far:

The gardening problem as a decision problem:

Input: List including the seed limit of each pot M=[m1,m2,...,mn], a list of pairs of seeds P={{fi, fj}} that cannot be planted together, positive integer K (goal).

Question: Is it possible to plant at least K different types of seeds?

(Should I exclude the "at least"?)

In order to show that the problem is NP-hard I need to reduce the NP-complete problem Independent set to the gardening problem.

IndependentSet(G=(V,E), K')=

M ← [K'] // Only one pot with capacity of K'
P ← E
K ← K'
return GardeningProblem(M, P, K)

The reduction is polynomial. I want to show that it is correct, i.e. there exists an independent set I with K nodes iff there exists seedbed S with K seeds that can be planted together.

If there is a solution to the IS problem of size K, we can put the K corresponding seeds into our pot - therefor if we can't put K seeds in our pot, there is no independent subset of size K.

Assume that I is an independent set in G with K nodes. Let S be the corresponding seeds I. Take two arbitrary seeds fi and fj in S and show that they can be planted together. The fact that I is an independent set means that:

vi,vj ∈ I → (vi, vj) ∉ E → {fi, fj} ∉ P → fi and fj can be planted together.

The other implication, assume there exists a seedbed S where |S| = K and seeds that can be planted together. Then:

fi,fj ∈ S → {fi, fj} ∉ P → (vi, vj) ∉ E → vi and vj are independent.

Thus, the proof is complete.

I get a bit confused by the fact that the pots can have different capacities, and I don't really know how to work with that. It feels like I am missing something and that I should take the different capacities of the pots into consideration in the proof. It is supposed to be an easy problem. Is there a better way to solve this?

And when I formulate the gardening problem as a decision problem, I'm not sure if the "Question" should be "...at least K different types of seeds" or just "...K different types of seeds" ? How do I know which one is correct?

If someone could tell me if something is missing it would be greatly appreciated!

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – Nathaniel
    Nov 27, 2022 at 11:20
  • $\begingroup$ I edited the post, hopefully it's a bit clearer what I need help with. $\endgroup$
    – kim120
    Nov 27, 2022 at 11:32
  • $\begingroup$ We require you to credit the original source of all copied material. See cs.stackexchange.com/help/referencing. $\endgroup$
    – D.W. ♦
    Nov 29, 2022 at 3:27
  • $\begingroup$ Cross-posted: stackoverflow.com/q/74586190/781723. Please do not post the same question on multiple sites. $\endgroup$
    – D.W. ♦
    Dec 7, 2022 at 4:08
  • $\begingroup$ We generally prefer that you not delete your question after receiving an answer. Part of our goal is to build up an archive of high-quality questions and answers, and people may be answering on that basis, so it can be impolite to answerers who are hoping that they are helping not only you but others as well. $\endgroup$
    – D.W. ♦
    Dec 7, 2022 at 4:19

1 Answer 1

Reset to default
0
$\begingroup$

The proof seems ok to me. The fact that you didn't use multiple capacities does not mean something went wrong: some problems are inherently more complex than others, and a reduction from a simpler problem to a more complex problem is generally easier.

For example, doing a reduction from the $\texttt{Clique}$ problem to the $\texttt{Subgraph isomorphism}$ problem is very straightforward: just ask if a $k$-clique is isomorphic to a subgraph of $G$.

For your other question, despite the problem of "at least $K$ seeds" and "exactly $K$ seeds" are slightly different, solving those is equivalent: the second one implies the first one, and if there is a solution planting more than $K$ seeds, there necessarily exists a solution planting exactly $K$. That's why you can just choose the variant you are more comfortable with.

Improve this answer
$\endgroup$
13
  • $\begingroup$ Thank you very much, I appreciate it! :) $\endgroup$
    – kim120
    Nov 27, 2022 at 15:48
  • $\begingroup$ I'm sorry if this is a stupid question but would it be wrong to formulate the question that the decision problem should answer like this: "Is it possible to plant K different types of seeds together in the same pot? @Nathaniel $\endgroup$
    – kim120
    Nov 27, 2022 at 20:04
  • $\begingroup$ I didn't understand the meaning of your question. $\endgroup$
    – Nathaniel
    Nov 29, 2022 at 22:42
  • $\begingroup$ I'm sorry if my question was unclear. I was wondering if it is wrong to formulate the question as " Is it possible to plant K different types of seeds together in the same pot?" as opposed to just saying "Is it possible to plant K different types of seeds (not necessarily in the same pot)"? @Nathaniel $\endgroup$
    – kim120
    Dec 2, 2022 at 16:45
  • $\begingroup$ Well this is a slightly different problem, but with such a formulation, it would be equivalent to the Independant set problem. $\endgroup$
    – Nathaniel
    Dec 2, 2022 at 16:50

Your Answer

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

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