El cálculo de distancias entre cadenas tiene aplicaciones en biología molecular, teoría musical y reconocimiento de patrones. Una medida, llamada distancia de reversión corta, tiene aplicaciones en el cálculo de distancias evolutivas. Se ha demostrado que este problema se puede reducir al cálculo de un conjunto independiente máximo en el grafo correspondiente que se construye a partir de las cadenas de entrada dadas. Los grafos construidos caen principalmente en una clase que llamamos grafos en capas. En un grafo en capas, cada capa se refiere a un subgrafo que contiene, como máximo, algunos vértices. Las aristas entre capas están restringidas a los vértices en capas adyacentes. Estudiamos los problemas de MIS, MVC, MDS, MCV y MCD en grafos en capas donde MIS calcula el conjunto independiente máximo; MVC calcula la cubierta mínima de vértices; MDS calcula el conjunto dominante mínimo; MCV calcula la cubierta mínima de vértices conectados; y MCD calcula el conjunto dominante mínimo conectado. MIS, MVC y MDS se ejecutan en tiempo polinómico si . MCV y MCD se ejecutan en tiempo polinómico si , donde . Si , para , entonces MIS, MVC y MDS se ejecutan en tiempo cuasipolinómico. Si , entonces MCV y MCD se ejecutan en tiempo cuasipolinómico.