𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Permuted max-algebraic eigenvector problem is NP-complete

✍ Scribed by P. Butkovič

Publisher
Elsevier Science
Year
2008
Tongue
English
Weight
129 KB
Volume
428
Category
Article
ISSN
0024-3795

No coin nor oath required. For personal study only.

✦ Synopsis

Let a ⊕ b = max(a, b) and a ⊗ b = a + b for a, b ∈ R := R ∪ {-∞} 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 ∈ R n×n find all x ∈ R n , x / = (-∞, . . . , -∞) T (eigenvectors) such that A ⊗ x = λ ⊗ x for some λ ∈ R. The present paper deals with the permuted eigenvector problem: Given A ∈ R n×n and x ∈ R 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.

📜 SIMILAR VOLUMES

The STO problem is NP-complete
The STO problem is NP-complete
✍ P. Krysta; L. Pacholski 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 233 KB

We prove that the problem STO of deciding whether or not a finite set E of term equations is subject to occur-check is in NP. E is subject to occur-check if the execution of the Martelli-Montanari unification algorithm gives for input E a set E ∪ {x = t}, where t = x and x appears in t. Apt et al. (

The maximum edge biclique problem is NP-
The maximum edge biclique problem is NP-complete
✍ René Peeters 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 93 KB

We prove that the maximum edge biclique problem in bipartite graphs is NP-complete.