In this paper, we focus on some specific optimization problems from graph
theory, those for which all feasible solutions have an equal size
that depends on the instance size.
Once having provided a formal definition of this class of
problems, we try to extract some of its basic properties; most of
these are deduced from the equivalence, under differential
approximation, between two versions of a problem π which only
differ on a linear transformation of their objective functions.
This is notably the case of maximization and minimization versions
of π, as well as general minimization and minimization with
triangular inequality versions of π. Then, we prove that some
well known problems do belong to this class, such as special cases
of both spanning tree and vehicles routing problems. In
particular, we study the strict rural postman problem
(called SRPP) and show that both the maximization and the
minimization versions can be approximately solved, in polynomial
time, within a differential ratio bounded above by 1/2.
From these results, we derive new bounds for standard ratio
when restricting edge weights to the interval [a,ta] (the
SRPP[t] problem): we respectively provide a 2/(t+1)- and a
(t+1)/2t-standard approximation for the minimization and the
maximization versions.