On finding cycle bases and fundamental cycle bases with a shortest maximal cycle

An undirected biconnected graph G with nonnegative integer lengths on the edges is given. The problem we consider is that of finding a cycle basis B of G such that the length of the longest cycle included in B is the smallest among all cycle bases of G. We first observe that Horton's algorithm [SIAM J. Comput. 16 (2) (1987) 358-366] provides a fast solution of the problem that extends the one given by Chickefing et al. [Inform. Process. Lett. 54 (1995) 55-58] for uniform graphs. On the other hand we show that. if the basis is required to be fundamental, then the problem is NP-hard and cannot be approximated within 2 - epsilon For All epsilon > 0, even with uniform lengths, unless P = NP. This problem remains NP-hard even restricted to the class of complete graphs; in this case it cannot be approximated within 13/11 - epsilon, For Allepsilon > 0, unless P = NP; it is instead approximable within 2 in general. and within 3/2 if the triangle inequality holds. (C) 2003 Elsevier B.V. All rights reserved.