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.

  • $\begingroup$ Is $|A \cap D| = 1 = |B \cap D|$ an optimal solution? What do you mean by densest? Did you also consider taking the complement of the graph? Then the problem might be related to finding the largest (balanced) induced bipartite subgraph. $\endgroup$ – Pål GD Nov 24 '18 at 18:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.