Computational complexity of long paths and cycles in faulty hypercubes

Abstract

The problem of existence of an optimal-length (long) fault-free cycle in the n-dimensional hypercube with f faulty vertices is NP-hard. This holds even in case that f is bounded by a polynomial of degree three (six) with respect to n.

On the other hand, there is a linear (quadratic) bound on f which guarantees that the problem is decidable in polynomial time. Similar results are obtained for paths as well as for paths between prescribed endvertices.

Keywords

• Faulty vertex
• long cycle
• long path
• hypercube
• NP-hard problem