I am stuck with problem and not getting much ideas. I have a graph with $N$ vertices and $M$ edges. I have to count number of ways I can choose a pair of set of vertices say $(p,q)$, such that every vertex belonging to the set $p$ is connected with every vertices belonging to set $q$ and vice versa.
Given the graph and the cardanality of $p$ and $q$, how to efficiently (polynomial time algorithm in terms of vertices and edges) compute the number of assignment?
Example:
Say the graph is of $4 (0,1,2,3)$ vertices and with edges: $$(0,2),(0,3),(1,2),(1,3),(2,0),(2,1),(2,3),(3,0),(3,1),(3,2)$$
cardanality of $p$ and $q$ be $1$ and $2$ respectively. Then there are $8$ possible assignments.
$$(\{0\},\{2,3\}), (\{1\},\{2,3\}), (\{2\},\{0,1\}),(\{2\},\{0,3\}),(\{2\},\{1,3\}),(\{3\},\{0,1\}),(\{3\},\{0,2\}),(\{3\},\{1,2\}) $$
This problem is in #P at least. The decision problem of "Does a bipartite graph has a complete bipartite subgraph $U, W$ with $|U| = |W| = \alpha$?" is NP-complete. Proof in On Bipartite and Multipartite Clique Problems.
Thus, it is unlikely to find a polynomial algorithm to solve this problem.