Computational complexity of long paths and cycles in faulty hypercubes

AbstractThe 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