Vertex ranking with capacity

Vertex ranking has many practical applications, ranging from VLSI layout and sparse matrix factorization to parallel query processing and assembly of modular products. Much research has been done on vertex ranking and related problems, polynomial time algorithms are known for a wide variety of graph classes as well as NP-hardness has been shown for other graph classes. In this paper we propose an extension to vertex ranking. Vertex ranking has many applications in computing a parallel schedule, but there is the assumption that the amount of parallel capacity is unbounded. Many applications do have restricted capacity, such as the number of processors or machines. Therefore we introduce vertex ranking with capacity. In this paper we show that vertex ranking and vertex ranking with capacity do not have a polynomial sized kernel, unless all coNP-complete problems have distillation algorithms. Having to deal with the NP- hardness of both problems, we give, to our knowledge, the first O *(2 n ) time exact algorithm for vertex ranking and use this for devising an O *(2.5875 n ) time algorithm for vertex ranking with capacity. We also show that we can transform vertex rankings to vertex rankings with capacity, and use this for a polynomial time algorithm that transforms an f(n)-approximate vertex ranking to a vertex ranking with capacity of at most f(n)¿+¿1 times the optimum size. Lastly, give an log(c) additive approximation for vertex ranking with capacity when restricted to trees and extend this to graphs of bounded treewidth