No, in the cases above, it is not a case of reducing a relative clause.
A relative clause is also called an adjective clause because it specifically modifies a noun. In the example,
The man who is sitting next to you is my cousin.
"who is sitting next to you" is a relative clause because it modifies "the man", in this case defining "which man".
However, in the sentence,
They denied that they had stolen the money.
"that they had stolen the money" does not modify any nouns. Therefore, it is not a relative clause. Since there is no relative clause, we can't reduce a relative clause.
Instead, what we're looking at is a reporting verb (like "say" or "tell"). Reporting verbs can generally take both a verb or a "that" clause as a compliment. For example:
He told me that he wanted me to go to the park.
He told me to go to the park.
For each reporting verb, the form of the verb may be either a gerund or an infinitive. In the case of "deny", that form is the gerund. So here, "deny stealing" is [reporting verb] + [gerund].
"Having stolen" is just a gerund of a perfect aspect (e.g., "had stolen"). So really, "denied stealing" is closer to "denied that they stole" than to "denied that they had stolen", though all mean about the same thing.
So in summary, it's not a reduction of a relative clause because there is no relative clause, instead it's using a gerund compliment of a reporting verb.