Solving more linear complementarity problems with Murty's bard-type algorithm

The linear complementarity problem (M|q) is to findw andz inR ⁿ such thatw–Mz=q,w0,z0,w ^t z=0, givenM inR ^n×n andq in . Murty's Bard-type algorithm for solving LCP is modeled as a digraph.Murty's original convergence proof considered allq inR ⁿ andM inR ^n×n , aP-matrix. We show how to solve more LCP's by restricting the set ofq vectors and enlarging the class ofM matrices beyondP-matrices. The effect is that the graph contains an embedded graph of the type considered by Stickney and Watson wheneverM is a matrix containing a principal submatrix which is aP-matrix. Examples are presented which show what can happen when the hypotheses are further weakened.