2
$\begingroup$

I have $N$ songs, $M$ instruments.

Each song requires one or more of the $M$ instruments in order to be played.

My $K-1$ friends and I want to learn to play $K$ different instruments, and we want to pick them such that we maximize the amount of songs we will can play.

How would I efficiently solve this? I'm sure this problem maps to some well known computational problem, but nothing comes to mind at the moment.

$\endgroup$
  • $\begingroup$ I don't understand your question. Suppose that some song requires drums, bass guitar and electric guitar. Even if you learn all three of those instruments, you're not going to be able to play the song, unless you have more arms than I do. $\endgroup$ – David Richerby Oct 7 '16 at 14:22
  • $\begingroup$ ;) This isn't really about me learning instruments. I do need to select K instruments that include the maximal amount of songs though. N and M are large enough that brute force seems unworkable. $\endgroup$ – larspars Oct 7 '16 at 14:37
  • $\begingroup$ This is unsolvable due to inefficient data. Even if weak, a Song - Instrument correlation has to be provided. $\endgroup$ – Redu Oct 7 '16 at 21:59
  • $\begingroup$ You can assume that a list of what instruments are required for each song is provided as input. $\endgroup$ – larspars Oct 7 '16 at 22:22
5
$\begingroup$

I don't know a canonical name for this problem, but unfortunately it's NP-hard, even when every song requires at most 2 instruments. The upshot is that it's extremely unlikely that any polynomial-time algorithm exists that will solve every instance of your problem. I'll show this by reduction from the NP-hard problem Maximum Clique, in which we are given an undirected graph $G = (V, E)$ and a positive integer $k$, and asked whether there exists a clique of size $k$ in the graph.

To construct an instance of your problem from the Maximum Clique Instance: Create a song $s_{uv}$ for every edge $(u, v)$ in $E$, and an instrument $t_v$ for every vertex $v$ in $V$, and make song $s_{uv}$ require the two instruments $t_u$ and $t_v$. Set $K$ (part of the input to your problem) equal to $k$ (part of the input to the Maximum Clique problem). Now run any algorithm that solves your problem on the just-created instance: if the answer is $\ge k(k-1)/2$ then return YES, otherwise return NO. (Clearly this procedure could work just as easily with an algorithm that solves the "pure decision" form of your problem, i.e., when a number $r$ is also given as part of the input, and the task is to determine whether it is possible to choose at most $K$ instruments such that at least $r$ songs can be played.)

It is easy to see that, if $G$ contains a clique of size at least $k$, then we must correctly get a YES answer: by assumption, there is a $k$-vertex clique, which comprises $k(k-1)/2$ vertex pairs, each of which are connected by an edge, so choosing the corresponding $k$ instruments satisfies the $k(k-1)/2$ corresponding songs.

In the other direction, suppose that the algorithm for your problem reports that at least $k(k-1)/2$ songs can be played; we need to show that this implies that there is a $k$-clique in $G$. Given that we permitted at most $k$ instruments to be chosen, there certainly cannot be more than $k(k-1)/2$ songs that we can play, since every song requires a distinct pair of instruments: so we can infer that exactly $k(k-1)/2$ songs can be played. But every choice of at most $k$ instruments that does not correspond to a $k$-clique in $G$ omits at least one of these $k(k-1)/2$ edges, and thus allows strictly fewer than this maximum possible number of songs to be played; thus the only subgraphs on at most $k$ vertices that can result in at least $k(k-1)/2$ edges are subgraphs that are $k$-cliques.

$\endgroup$
  • $\begingroup$ Thanks for the answer. It's getting late, and I may be missing something, but I think there might be a bug in the mapping to max-clique. When vertices represent instruments, and edges represent songs, a clique would be a set of instruments that all co-occur with each other in songs. This isn't quite what I'm after. If a solution is a set of instruments X that can play songs Y, every song in Y must fully playable by the instruments in X, but need not require every instrument in X. Some songs might only need a subset of the instruments. $\endgroup$ – larspars Oct 7 '16 at 22:19
  • $\begingroup$ I don't quite follow. Remember that we're mapping an arbitrary max clique instance to an instance of your problem, not the other way round. The idea is that if any instance of a known-to-be-hard problem can be "encoded" as an instance of your problem, then your problem must be hard too. $\endgroup$ – j_random_hacker Oct 7 '16 at 23:24
  • $\begingroup$ Yeah, you're right, it would be an instance of my problem, so the argument works. Well, sucks that it turns out to be NP hard, but thanks again for the solid answer! $\endgroup$ – larspars Oct 8 '16 at 10:55
  • $\begingroup$ You're welcome :) Yeah, it sucks that it turns out to be hard, but OTOH now you can just throw simple heuristics (like randomised local search) at the problem without feeling guilty ;) Formulation as an ILP would probably be your best shot for an exact solution to small problems; the LP relaxation should at least give you some OK lower bounds. $\endgroup$ – j_random_hacker Oct 8 '16 at 15:04

Your Answer

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

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