We consider the problem of finding a fundamental cycle ba- sis of minimum total weight in the cycle space associated with an undi- rected biconnected graph G, where a nonnegative weight is assigned to each edge of G and the total weight of a basis is defined as the sum of the weights of all the cycles in the basis. Although several heuristics have been proposed to tackle this NP-hard problem, which has several interesting applications, nothing is known regarding its approximability. In this paper we show that this problem is MAXSNP-hard and hence does not admit a polynomial-time approximation scheme (PTAS) unless P=NP. We also derive the first upper bounds on the approximability of the problem for arbitrary and dense graphs. In particular, for complete graphs, it is approximable within 4 + ε , for any ε > 0.
On the Approximability of the Minimum Fundamental Cycle Basis Problem
GALBIATI, GIULIA;
2004-01-01
Abstract
We consider the problem of finding a fundamental cycle ba- sis of minimum total weight in the cycle space associated with an undi- rected biconnected graph G, where a nonnegative weight is assigned to each edge of G and the total weight of a basis is defined as the sum of the weights of all the cycles in the basis. Although several heuristics have been proposed to tackle this NP-hard problem, which has several interesting applications, nothing is known regarding its approximability. In this paper we show that this problem is MAXSNP-hard and hence does not admit a polynomial-time approximation scheme (PTAS) unless P=NP. We also derive the first upper bounds on the approximability of the problem for arbitrary and dense graphs. In particular, for complete graphs, it is approximable within 4 + ε , for any ε > 0.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
