TDP on explicit relations is NP-complete.
To see that TDP is in NP, guess \(R_1,R_2\)  and verify the TD conditions.
We show hardness by a reduction from the NP-complete problem: Covering by Complete Bipartite Subgraphs (CCBS) (Problem GT18 at [1]}).
In the CCBS we are given a bipartite graph \(G\)  and \(k>0\) , and the problem is whether \(G\)  can be covered by \(k\)  complete bipartite subgraphs.
