Reducing the Optimality Gap of Strictly Fundamental Cycle Bases in Planar Grids

Ekkehard Köhler, Christian Liebchen, Romeo Rizzi, and Gregor Wünsch

combinatorial optimization, cycle bases, strictly fundamental cycle bases, approximation, average stretch

The Minimum Cycle Basis~(MCB) Problem is a classical problem in combinatorial optimization. This problem can be solved in O(m²n+mn²log(n)). Much faster heuristics have been examined in the context of several practical applications. These heuristics restrain the solution space to strictly fundamental cycle bases, hereby facing a significant loss in quality. We complement these experimental studies by explaning theoretically why strictly fundamental cycle bases~(SFCB) in general must be much worse than general MCB.

Alon et al. (1995) provide the first non-trivial lower bound for the minimum SFCB problem, which in general is NP-hard. For unweighted planar square grid graphs they achieve a lower bound of ln(2)/2048 n log₂n-O(n), where ln(2)/2048 ≈ 1/2955.

Introducing a new recursive approach, we are able to establish a substantially better lower bound. Our explicit method yields a lower bound of only 1/12 n log₂n+O(n). In addition, we provide an accurate way of counting a short strictly fundamental cycle basis that was presented by Alon et al. In particular, we improve their upper bound from 2n log₂n to only 4/3 n log₂n. We finally conclude that these bases miss the optimum only by a factor of at most~16---compared to about 5900 according to Alon et al.

Download as [PDF]