Reducibility among NP-Hard graph problems and boundary classes

Many NP-hard graph problems become easy for some classes of graphs. For example, coloring is easy for bipartite graphs, but NP-hard in general. So we can ask question like when does a hard problem become easy? What is the minimum substructure for which the problem remains hard? We use the notion of boundary classes to study such questions. In this paper, we introduce a method for transforming the boundary class of one NP-hard graph problem into a boundary class for another problem. If Pi and Gamma are two NP-hard graph problems where Pi is reducible to Gamma, we transform a boundary class of Pi into a boundary class of Gamma. More formally if Pi is reducible to Gamma, where the reduction satisfies certain conditions, then X is a boundary class of Pi if and only if the image of X under the reduction is a boundary class of Gamma. This gives us a relationship between boundary classes and reducibility among several NP-hard problems. To show the strength of our main result, we apply our theorem to obtain some previously unknown boundary classes for a few graph problems namely; vertex-cover, clique, traveling-salesperson, bounded-degree-spanning-tree, subgraph-isomorphism and clique-cover.