Permuted max-algebraic eigenvector problem is NP-complete

Let a circle plus b = max (a, b) and a circle times b = a + b for a, b is an element of (R) over bar:= R boolean OR {-infinity} and extend these operations to matrices and vectors as in conventional linear algebra. The following eigenvector problem has been intensively studied in the past: Given A is an element of (R) over bar (nxn) find all x is an element of (R) over bar (n), x not equal (-infinity,...,-infinity)(T) (eigenvectors) such that A circle times x = lambda circle times x for some lambda is an element of (R) over bar. The present paper deals with the permuted eigenvector problem: Given A is an element of (R) over bar (nxn) and x is an element of (R) over bar (n), is it possible to permute the components of x so that it becomes a (max-algebraic) eigenvector of A? Using a polynomial transformation from BANDWIDTH we prove that the integer version of this problem is NP-complete. (C) 2007 Elsevier Inc, All rights reserved.