Continuous reductions among combinatorial optimization problems

Summary

Many reductions among combinatorial problems are known in the context of NP-completeness. These reductions preserve the optimality of solutions. However, they may change the “relative error” of approximative solutions dramatically. In this paper, we apply a new type of reductions, called continuous reductions. When one problem is continuously reduced to another, any approximation algorithm for the latter problem can be transformed into an approximation algorithm for the former. Moreover, the performance ratio is preserved up to a constant factor. We relate the problem “Minimum Number of Inverters in CMOS-Circuits”, which arises in the context of logic synthesis, to several “classical” combinatorial problems such as “Maximum Independent Set” and “Deletion of a Minimum Number of Vertices (Edges) in Order to Obtain a Bipartite (Partial) Subgraph”.