Packing and Covering: New paradigms and Algorithms[HBNI Th211]

Abstract

Packing and Covering are some of the fundamental problems in graph theory. An H- P ACKING problem is, given a graph G, what is the maximum number of disjoint graphs in H one can find in G. Similarly in H-C OVERING problem we desire to find the minimum number of disjoint graphs in H that together constitute the graph G. Both these problems are extremely well studied and proved to be NP-hard. The C OVERING problems that we study encompasses the very well known H AMILTONICITY problems. In part 1 of our thesis we study these problems where H is the class of cycles/paths. We study these problems with respect to the standard parameter (solution size) as well as some well known structural parameter