New answers tagged combinatorics
0
votes
Selecting a submatrix of a binary matrix NP hard?
Your problem is NP-hard. In particular, it is equivalent to maximum edge weight biclique problem (MWBP), which is known to be NP-hard.
Maximum edge weight biclique
MWBP is the following problem: ...
D.W.♦
- 152k
0
votes
Accepted
Densest Sub Graph and forbidden Pairs
The problem is NP-hard. (It is at least as hard as maximum independent set, which can be seen by setting $G$ to be the fully connected graph.)
Therefore, a reasonable approach is to use an off-the-...
D.W.♦
- 152k
Top 50 recent answers are included