A space-time tradeoff for permutation problems
Mikko Koivisto, Pekka Parviainen · 2010
Many combinatorial problems—such as the traveling salesman, feedback arcset, cutwidth, and treewidth problem— can be formulated as finding a feasible permutation of n elements. Typically, such problems can be solved by dynamic programming in time and space O ∗ (2 n), by divide and conquer in time O ∗ (4 n) and polynomial space, or by a combination of the two in time O ∗ (4 n 2 −s) and space O ∗ (2 s) for s = n, n/2, n/4,.... Here, we show that one can improve the tradeoff to time O ∗ (T n) and space O ∗ (S n) with T S < 4 at any √ 2 < S < 2. The idea is to find a small family of “thin ” partial orders on the n elements such that every linear order is an extension of one member of the family. Our construction is optimal within a natural class of partial order families. 1