PDP on explicit relations is NP-complete. Membership in NP is easily shown. We show hardness by reduction from Set Cover (Problem SP5 in [1]}). In Set Cover we are given a set of elements \(S=\lbrace a_1,\cdots a_n\rbrace \) , a set of subsets of \(S\) , \(C= \lbrace c_1,\cdots c_m\rbrace \)  and \(k\ge 0\) . The problem is whether there are \(k\)  sets from \(C\)  whose union covers \(S\) . We assume w.l.o.g. that every member of \(S\)  belongs to at least one member of \(C\) .
Given an instance \(I=(S,C,k)\)  of Set Cover, define a PDP instance \(I^{\prime }\)  where
\(\mathcal {I}=S\) , \(\mathcal {O}=C\)  , \(R=\lbrace (a,c) \mid a\in c\rbrace \)  and add the intermediate domain elements to be \(\mathcal {B}=\lbrace b_1,\cdots b_k\rbrace \) .
Assume that there is a set cover \(\lbrace c_{i_1},\cdots c_{i_k}\rbrace \subseteq C\)  for \(S\) . Then construct \(R_1,R_2\)  as follows. For every element \(a\)  and \(j\le k\) , set \((a,b_j)\in R_1\)  iff \(c_{i_j}\)  is the first set for which \(a\in c_{i_j}\) . In addition
set \((b_j,c_{i_j})\in R_2\) . Then \(R_1\subseteq \mathcal {I}\times \mathcal {B}\) , \(R_2\subseteq \mathcal {B}\times \mathcal {O}\)  and \(Img(R_1)\subseteq Dom(R_2)\) .
Since the set cover for \(S\)  covers all elements of \(S\) , we have that \(Dom(R_1\circ R_2)=Dom(R)\) .
To see that \(R_1\circ R_2\subseteq R\) , let \((a,c_{i_j})\in R_1\circ R_2\)  for some \(j\le k\) . Then \((a,b_j)\in R_1\)  and \((b_j,c_{i_j})\in R_2\) . By definition of \(R_1\) , \(a\in c_{i_j}\) , therefore we have that \((a,c_{i_j})\in R\) .
