Digraph Models of Bard-Type Algorithms for the Linear Complementarity Problem

For M ∈ E^n×n and q ∈ Eⁿ, the linear complementarity problem is to find vectors w, z ∈ Eⁿ such that w − Mz = q, w ≥ 0, z ≥ 0, w^tz = 0. A family of algorithms based on complementary pivoting for solving this problem is modelled by digraphs. These digraphs show that such algorithms can cycle even for symmetric, positive deFinite M, and provide some insight into the algorithms' behavior. For a P-matrix M, it is proved that if the solution to the complementarity problem can be obtained by k principal pivots, then it can be obtained by k Bard-type pivots. Furthermore, the digraphs provide simple geometric proofs of some of Murty's algebraic results. The digraphs, apart from their use as models, also raise some interesting graph-theoretic questions.