1
$\begingroup$

In the course of my research, I came across a graph matching problem for bipartite graphs, and I am wondering if this particular problem has appeared in the literature before. I suspect it is NP-complete.

The problem assumes a bipartite graph with $N_1$ nodes in the first partition, and $N_2$ nodes in the second, with both $N_{1,2}$ even. Each node is then assigned to one of two clusters, $A$, or $B$, with the restriction that both clusters contain precisely half the nodes for each partition, $N_1/2$ and $N_2/2$. The problem is then to find the cluster assignment that minimizes the number of edges between nodes in different clusters, i.e. the number of times the A/B partitioning cuts the graph edges.

A potential source of confusion here is that there are 2 notions of partitions. The first notion is intrinsic to the original bipartite graph -- there are two sets of vertices, and there are no edges within a set. The second notion is the partitioning asked for by the problem. To avoid confusion I have called this second notion clustering.

$\endgroup$
3
  • $\begingroup$ What is your question? You haven't actually asked anything. $\endgroup$ Feb 6 '18 at 0:24
  • $\begingroup$ I am wondering if this particular problem has appeared in the literature before $\endgroup$ Feb 6 '18 at 0:45
  • $\begingroup$ Can you formalize the problem in question ? $\endgroup$
    – Neel Basu
    Feb 19 '18 at 14:06
1
$\begingroup$

The question does not formalize the problem. However What I understood from the question there is a similar problem known to be NP-complete.

Balanced Complete Bipartite Subgraph Problem

Given bipartite graph $G=(V,E)$ and $K\leq \vert V \vert$ are there two disjoint sets $V_{1}, V_{2}\subseteq V$ such that $\vert V_{1} \vert = \vert V_{2} \vert = K$ and $u\in V_{1}, v\in V_{2}$ implies $(u,v)\in E$

Hope this helps.

$\endgroup$
3
  • $\begingroup$ Thanks, can you point me to a reference please? $\endgroup$ Feb 20 '18 at 3:56
  • $\begingroup$ Garrey Jonson computers and intractability $\endgroup$
    – Neel Basu
    Feb 20 '18 at 4:10
  • $\begingroup$ Check appendix Page 196 GT 24 $\endgroup$
    – Neel Basu
    Feb 20 '18 at 4:19

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.