Permuted max-algebraic eigenvector problem is \(NP\)-complete (Q2479500)

The aim of the paper is to prove the NP-completeness of the following permuted eigenvector problem: ``Given \(A\in\overline{\mathbb R}^{n\times n}\) and \(x\in\overline{\mathbb R}^n,\) (\(\overline{\mathbb R}=\mathbb R\cup{-\infty}\)), it is possible to permute the components of \(x\) so that it becomes a (max-algebraic) eigenvector of \(A\)?'' The first section is an introduction in nature. The second section focuses on the \(NP\)-completeness. The author proves that the integer permuted eigenvector problem: ``Given \(A\in\mathbb{Z}^{n\times n}\) and \(x\in\mathbb{Z}^n,\) is there a \(\pi\in P_n\) (the set of permutations of the set \({1,2,\dots,n}),\) such that \(x(\pi)\) is an eigenvector of \(A\)?'' is NP-complete for the class of normalised, strongly regular matrices and the NP-completeness for all integer matrices then immediately follows. The conclusions are presented in the third section.