# What kind of NP problem would this be

I have N by N symmetrical matrix with each side having the same items.

     A    B    C    D
A    0
B    4    0
C    8    3    0
D    3    1    8    0


In reality this would be much larger (100 x 100)

I am trying to find a subset of a fixed size in this matrix with the highest score. For example the selection ABC would be:

  AB = 4;
AC = 8;
BC = 3;
Total  15


It is kinda like traveling salesman problem, but with the final distance only determined by the final selection.

• What do you mean by "subset"? Wouldn't the set of all positive entries be the trivial solution? Oct 7, 2013 at 15:29
• The subset is of a fixed size. In the current example it would be 3. In the the 100x100 matrix, I would like to select 20 items that would result in the maximum score.
– KWG
Oct 7, 2013 at 15:42

You can reduce clique (or independent set) to your problem, so it is NP-hard. Just take the adjacency matrix as your matrix, use the same parameter $k$ (the size of the clique), and declare that there is a clique in the graph if the maximum score is $\binom{k}{2}$.

Is $k$ fixed or not? Fixed means that $k$ is the same for every input, whether it's $3\times 3$ or $1000000\times 1000000$. If $k$ is fixed, then there are fewer than $n^k$ possible subsets so you get a deterministic polynomial-time algorithm just by trying each subset in turn.

On the other hand, if $k$ varies, either by being a part of the input or by being a function of $n$, then the problem is (probably) NP-complete. If it's part of the input, Yuval has shown NP-completeness by reduction from clique. If it's some function $f(n)$ and $f$ can be computed efficiently enough, you get NP-completeness roughly like this, again by reduction from clique.

We want to know if an $m$-vertex graph $G$ has a clique of size at least $k$. First, find some $k'\geq k$ such that $f(n)=k'$ for some $n\geq m$. Then, add $k'-k$ vertices to $G$ and make each one adjacent to every vertex in the new graph $G'$ (including the new vertices). Finally, add isolated vertices to $G'$ to give a graph $G''$ with $n$ vertices in total. (You'll need to deal with the case where $G'$ already has more than $n$ vertices!)

Now, $G$ has a $k$-clique if, and only if, $G'$ has a $k'$-clique if, and only if, $G''$ has a $k$-clique. But $k'=f(n)$ and the adjacency matrix of $G''$ is $n\times n$, so we can use Yuval's answer to determine if $G''$ has a $k'$-clique.

• Thanks, tbh this is clearly not my expertise so I right now I am reading up on the clique NP problems. But to answer your question if k is fixed, yes it is.
– KWG
Oct 14, 2013 at 8:43
• OK. So, in that case, it's polynomial time (so presumably not NP-complete). Of course, if $k$ is bigger than 5 or 6 and $N$ is large, it might not be feasible to check all $N^k$ possible solutions. In that case, you've run into one of those cases where equating "polynomial" with "efficient" isn't so helpful. Oct 15, 2013 at 7:38