## Abstract

In this paper, we consider the sparse linear complementarity problem, denoted by k-LCP: the coefficient matrices are restricted to have at most k nonzero entries per row. It is known that the 1-LCP is solvable in linear time, and the 3-LCP is strongly NP-hard. We show that the 2-LCP is strongly NP-hard, and it can be solved in polynomial time if it is sign-balanced, i.e., each row of the matrix has at most one positive and one negative entry. Our second result matches the currently best-known complexity bound for the corresponding sparse linear feasibility problem. In addition, we show that an integer variant of the sign-balanced 2-LCP is weakly NP-hard and pseudo-polynomially solvable, and the generalized 1-LCP is strongly NP-hard.

Original language | English |
---|---|

Pages (from-to) | 1015-1026 |

Number of pages | 12 |

Journal | Mathematics of Operations Research |

Volume | 40 |

Issue number | 4 |

DOIs | |

Publication status | Published - 2015 Nov |

Externally published | Yes |

## Keywords

- Combinatorial algorithm
- Linear complementarity problem
- NP-hardness
- Polynomial solvability
- Two-variable constraints

## ASJC Scopus subject areas

- General Mathematics
- Computer Science Applications
- Management Science and Operations Research