Abstract (EN)

We conceive some approximability preserving (continuous) reductions among a number of combinatorial problems. The preservation of the approximation ratio along these reductions establishes a kind of continuity between the involved problems, continuity resulting to a possible transfer (up to multiplication by the so called expansion of the reduction) of positive, negative or conditional results along chains of such reductions. We are, more particularly interested in continuity of reductions in the interior of hierarchies of combinatorial problems as well as, given that approximability preserving reductions are composable and transitive, we explore the continuity of reductions between members of different hierarchies. For a combinatorial problem, a hierarchy is obtained when we impose additional restrictions on its instances. We construct first a hierarchy for set covering problem and we explore the completeness of its members under reductions that preserve their approximation ratio (continuous reductions). We construct also a hierarchy for hitting set and we give continuity results for it. Moreover, we relate another NP-complete database query optimization problem, the minimal join problem to set covering hierarchy by proposing a reduction and by proving its continuity. After, we establish hierarchies for the vertex covering by cliques problem as well as for the vertex covering problem. For the members of each hierarchy we investigate the continuity of reductions relating them. Also, we propose such reductions connecting problems from distinct hierarchies. So, subclasses of NP-complete problems related by approximability preserving reductions are systematically constructed.