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 Wahlström (STACS 2013).

Steiner Cycle

is a generalization of

Hamiltonian Cycle

and asks, given a graph

$$G=(V,E)$$

and a set of

$$k$$

terminals

$$T\subseteq V$$

, whether there is a simple cycle containing

$$T$$

as well as an arbitrary number of further vertices of

$$G$$

. Wahlström’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

$${\mathcal {O}}(2^k\cdot |V|^c)$$

algebraic algorithm also due to Wahlström. 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.