but this algorithm is again not fixed-parameter tractable (for the parameter "cyclomatic number") because the exponent in the polynomial depends on the cyclomatic number. There exist fixed-parameter tractable algorithms to solve the metric dimension problem for the parameters "vertex cover", "max leaf number", and "modular width". Graphs with bounded cyclomatic number, vertex cover number or max leaf number all have bounded treewidth, however it is an open problem to determine the complexity of the metric dimension problem even on graphs of treewidth 2, that is, series–parallel graphs. Approximation complexity The metric dimension of an arbitrary n-vertex graph may be approximated in polynomial time to within an approximation ratio of by expressing it as a set cover problem, a problem of covering all of a given collection of elements by as few sets as possible in a given family of sets. In the set cover problem formed from a metric dimension problem, the elements to be covered are the pairs of vertices to be distinguished, and the sets that can cover them are the sets of pairs that can be distinguished by a single chosen vertex. The approximation bound then follows by applying standard approximation algorithms for set cover. An alternative greedy algorithm that chooses vertices according to the difference in entropy between the equivalence classes of distance vectors before and after the choice achieves an even better approximation ratio, . This approximation ratio is close to best possible, as under standard complexity-theoretic assumptions a ratio of cannot be achieved in polynomial time for any . The latter hardness of approximation still holds for instances restricted to subcubic graphs, and even to bipartite subcubic graphs. References Notes Bibliography . . . . . . . . . . . A1.5: GT61, p. 204. . . . . . . . . . . Graph invariants