2
$\begingroup$

I am a biologist doing some computational work. I encountered a problem and need some help since I don't have much algorithmic background.

The problem:
Assume we have a non-directed, weighted graph, in which every node has some categorical attribute, e.g. color. I want to break the graph into sub-graphs in which there is at most one node of each color. Decisions should be made by trying to preserve the strongest connections (edges with highest weights). For example, let's look at the graph below (I didn't include weights as this would be hard to see):
enter image description here
In this case, I would like to break the graph into two sub-graphs (assuming that this is what the weights indicate): enter image description here
Two notes (I don't know if they matter though):

  • The maximal number of colors is known in advance
  • After the graph was broken, I don't really care about the topology anymore - I just want to know which nodes ended up together.

My questions:
My first question is: does this look familiar to you? Has this problem been solved before? Maybe it's a variant of something every CS student learns? If so, can you please refer me to relevant information/literature?
If not, Then I'd like some help on how to approach this. Can you give some ideas on how to start developing and algorithm that can solve this type of problem?
Any other advice would be useful. Thank you!

$\endgroup$
2
$\begingroup$

This seems to be the "minimum weight orthogonal partition problem", which has been studied among others by Zheng et al. [1]. Computer scientists have also studied it under the name "colourful components", though it sometimes refer to an unweighted variant. The problem is known to be NP-hard, and some approximations exist [2]. There are probably more recent results, these two references should help you find them.

[1]: Chunfang Zheng, Krister M. Swenson, Eric Lyons, David Sankoff: OMG! Orthologs in Multiple Genomes - Competing Graph-Theoretical Formulations. WABI 2011: 364-375 -- http://albuquerque.bioinformatics.uottawa.ca/kms/files/papers/2011-ZhengOMG.pdf

[2]: G. He, J. Liu and C. Zhao: Approximation Algorithms for Some Graph Partitioning Problems. Graph Algorithms and Applications 2, pp. 21-31 (2004) -- https://www.researchgate.net/publication/220639657_Approximation_Algorithms_for_Some_Graph_Partitioning_Problems

$\endgroup$
  • $\begingroup$ Thank you very much! Indeed my problem is related to orthology sets, and it seems that Sankoff's group had already tackled the problem. Any idea if these algorithms have been implemented in any software package? $\endgroup$ – soungalo Jan 8 at 19:26
  • $\begingroup$ Not that I'm aware, and nothing of the sort appears on David Sankoff's software page. But the paper shows experimental results, so I'd ask him directly if there's anything he or his students can share. $\endgroup$ – Anthony Labarre Jan 8 at 20:03

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.