Parameterized Complexity of Sparse Linear Complementarity Problems

In this paper, we study the parameterized complexity of the linear complementarity problem (LCP), which is one of the most fundamental mathematical optimization problems. The parameters we focus on are the sparsities of the input and the output of the LCP: the maximum numbers of nonzero entries per row/column in the coefficient matrix and the number of nonzero entries in a solution. Our main result is to present a fixed-parameter algorithm for the LCP with the combined parameter. We also show that if we drop any of the three parameters, then the LCP is NP-hard or W[1]-hard. In addition, we show the nonexistence of a polynomial kernel for the LCP unless coNP \(\subseteq \) NP/poly.

The authors thank the referees for their valuable comments on this manuscript. The first author is supported by Grant-in-Aid for JSPS Fellows, and by JST, ERATO, Kawarabayashi Large Graph Project. The second author is supported by JSPS KAKENHI Grant Numbers 25730001 and 24106002, and by JST, ERATO, Kawarabayashi Large Graph Project. The third author is supported by JSPS KAKENHI Grant Numbers 24106002 and 26280001.

Authors and Affiliations

1. JST, ERATO, Kawarabayashi Large Graph Project, National Institute of Informatics, Tokyo, 101-8430, Japan

   Hanna Sumita

2. Graduate School of Arts and Sciences, University of Tokyo, Tokyo, 153-8902, Japan

   Naonori Kakimura

3. Research Institute for Mathematical Sciences, Kyoto University, Kyoto, 606-8502, Japan

   Kazuhisa Makino

Corresponding author

Correspondence to Hanna Sumita.

Appendix 1: Reduction of the LCP to the \(3\)-Column-Sparse LCP

In this section, we prove the following proposition.

Proposition 5.9

The LCP is polynomially reducible to the \(3\)-column-sparse LCP.

Proof

Let \(\mathrm{LCP}\left( M, q\right) \) be an LCP instance of order n. We transform it to an equivalent \(3\)-column-sparse LCP instance as follows.

For each \(j=1, \ldots , n\), let \(m^{i, j}\) be a vector whose i-th entry is \(M_{ij}\) and others are zero. Note that \(M_{*j} = \sum _{i=1}^n m^{i,j}\). Thus \(\mathrm{LCP}\left( M, q\right) \) is equivalent to finding a vector z satisfying

For each variable \(z_j \ (j = 1, \ldots , n)\), we introduce n copies \(z^1_j, \ldots , z^n_j\) of \(z_j\). Then (25) is equivalent to the following system:

and

for \(j=1, \ldots , n\).

We observe that (27) can be rewritten as \(z_j \ge z^1_j \ge \dots \ge z^n_j \ge z_j\). Thus by introducing a new variable \(z^0_j\), we replace (27) with linear inequalities with complementarity conditions:

where we denote \(z^{n+1}_j = z_j\).

Let \(\mathrm{LCP}\left( M', q'\right) \) be an LCP instance defined by (26) and (28). We see that \(\mathrm{LCP}\left( M, q\right) \) is equivalent to \(\mathrm{LCP}\left( M', q'\right) \), and \(\mathrm{LCP}\left( M', q'\right) \) has \(n(n+2)\) variables by construction. In addition, each variable appears at most three times in the first linear inequalities in (26) and (28), which implies that \(\mathrm{LCP}\left( M', q'\right) \) is \(3\)-column-sparse. \(\square \)

Appendix 2: The \(1\)-Column-Sparse LCP

In this section, we show that the \(1\)-column-sparse LCP is solvable in linear time. Our algorithm finds an index set X such that any solution z of the LCP satisfies \(z_X = {\varvec{0}}\), by using the following lemma.

Lemma 5.10

For any vector a and any number \(b \ne 0\), we have the following statement.

1. (a)

   \(b< 0, \ a \le {\varvec{0}}\Leftrightarrow a^\top x + b < 0\) for all vectors \(x \ge {\varvec{0}}\).

2. (b)

   \(b> 0, \ a \ge {\varvec{0}}\Leftrightarrow a^\top x + b > 0\) for all vectors \(x \ge {\varvec{0}}\).

3. (c)

   \(a_i /b < 0\) for some index i \(\Leftrightarrow a^\top x + b = 0\) has a solution \(x \ge {\varvec{0}}\) with exactly one positive entry \(x_i\).

Proof

It is easy to see (a) and (b). We show (c). If we have an index i with \(a_i /b < 0\), then the vector x defined by \(x_i = -b/a_i > 0\) and \(x_j = 0 \ (j \ne i)\) satisfies \(a^\top x + b = 0\). Conversely, if we have a vector x such that \(a_i x_i + b = 0\) for some i with \(x_i > 0\), then we have \(a_i / b = -1/x_i < 0\). \(\square \)

Let \(\mathrm{LCP}\left( M, q\right) \) be a \(1\)-column-sparse LCP instance. If \(q_i < 0\) and \(M_{i *} \le {\varvec{0}}\) for some i, then \((Mz+q)_i = M_{i *} z + q_i \ge 0, \ x \ge {\varvec{0}}\) is never satisfied by (a) in Lemma 5.10, and \(\mathrm{LCP}\left( M, q\right) \) has no solution. If \(q_i > 0\) and \(M_{i *} \ge {\varvec{0}}\), then by (b) in Lemma 5.10, \((Mz+q)_i > 0\) for all \(x \ge {\varvec{0}}\), which implies that any solution z of \(\mathrm{LCP}\left( M, q\right) \) satisfies \(z_i = 0\) by the complementarity. Using these observations, our algorithm finds a solution of \(\mathrm{LCP}\left( M, q\right) \) as follows.

For each \(i = 1, \ldots , n\), let \(T_i = \{j \mid M_{ij} > 0\}\) if \(q_i <0\), and \(T_i = \{j \mid M_{ij} < 0\}\) if \(q_i > 0\). Set \(S = [n]\).

Find an index \(i \in S\) with \(q_i \ne 0\) and \(T_i = \emptyset \). If \(q_i < 0\), then \(\mathrm{LCP}\left( M, q\right) \) has no solution. Otherwise, set \(S \leftarrow S {\setminus } \{i \}\), and set \(T_j \leftarrow T_j {\setminus } \{i\}\) for each j with \(i \in T_j\).

Repeat the above procedure until \(T_i \ne \emptyset \) holds for any \(i \in S\) with \(q_i \ne 0\), i.e., \(q_i = 0\) or \(\frac{1}{q_i} M_{iS} \not \ge {\varvec{0}}\) for all \(i \in S\). For each \(i \in S\) with \(q_i =0\), let \(x^i = {\varvec{0}}\in {\mathbb {R}}^S\). For \(i \in S\) with \(q_i \ne 0\), let \(x^i\) be a solution of \(M_{iS} x^i+q_i = 0, \ x^i \ge {\varvec{0}}\), which can be found in linear time by using (c) in Lemma 5.10. Since \(\mathrm{LCP}\left( M, q\right) \) is \(1\)-column-sparse, the sets of variables appearing in \(M_{i *} z + q_i \ge 0 \ (i \in S)\) are disjoint from each other. Thus the vector \(x=\sum _{i\in S}x^i\) satisfies \(M_{SS} x+ q_S = {\varvec{0}}\). Therefore, since we have \(M_{\overline{S}S} x + q_{\overline{S}} \ge {\varvec{0}}\), the vector z with \(z_S = x\) and \(z_{\overline{S}} = {\varvec{0}}\) is a solution of \(\mathrm{LCP}\left( M, q\right) \).

Thus we obtain the following proposition.

Proposition 5.11

The \(1\)-column-sparse LCP is solvable in linear time.

Reprints and permissions