I'm searching (without results) a problem that can be reduced to finding the densest subgraph with the same cardinality between two classes of nodes.
Consider a graph with nodes of class A and nodes of class $B$ (not bipartite and $|A|$ it is not necessarily the same as $|B|$). The problem is to find the densest subgraph that respects the costraint $|A\cap D|=|B\cap D|$ where $D$ is the set of the nodes of the desired subgraph.
Before asking I tried with the partition problem, but the transformation between partition in this problem is pseudo polynomial and not polynomial (for each number N in the input set i build a clique of N nodes so the transformation depends on the value of the numbers in the set and this is not ok).
Thanks for the help :)
Edit: the definition of densest is the subgraph that maximizes #edges/#nodes. This subgraph can be computed in polynomial time with an algorithm by Goldberg.