Minimum Weakly Fundamental Cycle Bases Are Hard To Find

In the last years, new variants of the minimum cycle basis (MCB) problem and new classes of cycle bases have been introduced, as motivated by several applications from disparate areas of scientific and technological inquiry. At present, the complexity status of the MCB problem is settled only for undirected, directed, and strictly fundamental cycle bases (SFCB's). Weakly fundamental cycle bases (WFCB's) form a natural superclass of SFCB's. A cycle basis C = {C-1, C-2, ... , C-nu} of a graph G is a WFCB iff nu = 0 or there exists an edge e of G and a circuit C-i in C such that C \ C-i is a WFCB of G \ e. WFCB's still possess several of the nice properties offered by SFCB's. At the same time, several classes of graphs enjoying WFCB's of cost asymptotically inferior to the cost of the cheapest SFCB's have been found and exhibited in the literature. Considered also the computational difficulty of finding cheap SFCB's, these works advocated an in-depth study of WFCB's. In this paper, we settle the complexity status of the MCB problem for WFCB's (the MWFCB problem). The problem turns out to be APX-hard. However, in this paper, we also offer a simple and practical 2inverted right perpendicularlog(2) ninverted left perpendicular-approximation algorithm for the MWFCB problem. In O(n nu) time, this algorithm actually returns a WFCB whose cost is at most 2inverted right perpendicularlog(2)ninverted left perpendicular Sigma(e is an element of E(G)) w(e), thus allowing a fast 2inverted right perpendicularlog(2)ninverted left perpendicular-approximation also for the MCB problem. With this algorithm, we provide tight bounds on the cost of any MCB and MWFCB.