HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

What kind of NP problem would this be

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thisproblemwhatwouldkind

Problem

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.

Solution

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

Context

StackExchange Computer Science Q#14886, answer score: 2

Revisions (0)

No revisions yet.