An Experimental Analysis of a Polynomial Compression for the Steiner Cycle Problem

摘要

We implement and evaluate a polynomial compression algorithm for the Steiner Cycle problem that was recently developed by Wahlstrom (STACS 2013). Steiner Cycle is a generalization of Hamil-tonian Cycle and asks, given a graph G = (V, E) and a set of k terminals T is contained in V, whether there is a simple cycle containing T as well as an arbitrary number of further vertices of G. Wahlstroem's compression algorithm takes any such instance and in polynomial time produces an equivalent instance of size polynomial in k. The algorithm has several distinguishing features that make it interesting as a test subject for evaluating theoretical results on preprocessing: It uses Gaussian elimination on the Tutte matrix of (essentially) the input graph instead of explicit reduction rules. The output is an instance of an artificial matrix problem, which might not even be in NP, rather than Steiner Cycle. We study to what extend this compression algorithm is useful for actually speeding up the computation for Steiner Cycle. At high level, we find that there is a substantial improvement of using the compression in comparison to outright running a O(2~k · |V|~c) algebraic algorithm also due to Wahlstroem. This is despite the fact that, at face value, the creation of somewhat artificial output instances by means of nonstandard tools seems not all that practical. It does benefit, however, from being strongly tied into a careful reorganization of the algebraic algorithm.