3
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ What do you mean by "subset"? Wouldn't the set of all positive entries be the trivial solution? $\endgroup$
    – G. Bach
    Oct 7, 2013 at 15:29
  • $\begingroup$ 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. $\endgroup$
    – KWG
    Oct 7, 2013 at 15:42

2 Answers 2

Reset to default
2
$\begingroup$

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}$.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – KWG
    Oct 14, 2013 at 8:43
  • $\begingroup$ 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. $\endgroup$
    – David Richerby
    Oct 15, 2013 at 7:38

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.