They both work and are frequently used. The use of "absolute" is a bit stronger...no deviation from honesty, even for things like politeness, has a place in this relationship.
The use of "with" here is a little unusual. I'd be more likely to say
This is a relationship based on complete honesty.
This is a relationship of complete honesty
The former implies that honesty was the founding principle of the relationship from the beginning.
The latter does not. If we had a relationship and we decided somewhere along the way that we would be completely honest with each other, we would use the latter. However, the latter also may imply that honesty is not only a feature of our relationship, but is the relationship itself.
In both examples, either "complete" or "absolute" would be acceptable.