Linear time transformations between combinatorial problems

Abstract

Besides showing the existence of NP-complete problems, Cook's theorem and subsequent developments have resulted in a large number of polynomial-time transformations between combinatorial problems. For both theoretical and practical reasons it is important to pursue these transformations, especially low-order ones. In this paper, two linear classes are displayed: it is shown that satisfiability, 3-colourability and set-splitting are linear-time equivalent. It is also shown that bipartite matching and path-connectivity are linear-time equivalent. The computational model on which these results are based is a 1-tape transducer.