Actually, it seems my problem has been studied in the following paper:
- M. C. Golumbic,T. Hirst, M. Lewenstein, Uniquely Restricted Matchings, Algorithmica, Volume 31, Issue 2, October 2001.
The authors proved the problem of finding the largest triangular submatrix is NP-complete. However, they do not provide any algorithm.
