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^tz=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.