0
$\begingroup$

Given the following:

"You are organizing a party and you want it to be as much fun as possible. You have $n$ friends to choose from, but the maximum number of people that you can invite into your flat — its capacity — is $C$. The fun at a party stems from pairwise interactions between guests, and you have the an $n \times n$ “fun table” $F$, such that for every pair $(i,j)$ of your friends, $F[i,j]$ is a number between 0 and 1 that specifies how much fun their mutual presence at the party would contribute. The DECENT-PARTY decision problem is—given an $n\times n$ array $F$ representing the fun table, a number $C$ and a number $T$ as inputs—to determine if there is a selection of $C$ guests such that the total fun contributed by all pairwise interactions between them is at least $T$."

How can I prove that if there is a polynomial time algorithm for solving DECENT-PARTY then there is also one for the INDEPENDENT-SET decision problem? In order to do this I want to show a polynomial time reduction from INDEPENDENT-SET to DECENT-PARTY, i.e. that DP is at least as hard as IS and thus it follows.

To do this, I think I need to instantiate IS, a graph and some integer $k$. Then somehow translate that to an instance of DP but I am not sure how as it seems that DP involves non-integer values.

$\endgroup$
  • $\begingroup$ You will need to reduce in the other direction: Show how to transform an arbitrary instance of Independent Set into an instance of Decent-Party with the same answer (YES or NO). $\endgroup$ – j_random_hacker Apr 24 '18 at 15:58
  • $\begingroup$ @j_random_hacker I was more just stating some of my thoughts on similar reductions, I think I need to have nodes each with an associated weight, then want to find a maximal independent set in terms of the sum of those weights. However, I am not sure how to determine edges between nodes. $\endgroup$ – Harrison W. Apr 24 '18 at 16:08
  • $\begingroup$ Attempting reductions in the wrong direction is probably the most common mistake made by students, and while your second paragraph doesn't outright say that you are trying to reduce DP to IS, it all but does say it: It reads like you think that if you could reduce DP to BMM then you could reduce BMM to IS and your goal would be achieved, but it would not because this reduction (from DP to IS) is in the wrong direction. $\endgroup$ – j_random_hacker Apr 24 '18 at 16:22
  • $\begingroup$ @j_random_hacker I will edit to try and clarify $\endgroup$ – Harrison W. Apr 24 '18 at 16:24
  • $\begingroup$ You need to reduce IS to DP. That means that you have to come up with a way to convert any instance of IS (a graph, and a threshold $k$) that I give you into an instance of DP. Your input is the graph; you need to somehow encode the edges in it as a "fun table". (You never "determine edges between nodes"; you are given those as part of the input.) $\endgroup$ – j_random_hacker Apr 24 '18 at 16:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.