patternMinor
Algorithm for breaking a graph into sub-graphs based on an attribute
Viewed 0 times
graphintographssubbreakingalgorithmforbasedattribute
Problem
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):
In this case, I would like to break the graph into two sub-graphs (assuming that this is what the weights indicate):
Two notes (I don't know if they matter though):
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!
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):
In this case, I would like to break the graph into two sub-graphs (assuming that this is what the weights indicate):
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!
Solution
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
[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
Context
StackExchange Computer Science Q#119325, answer score: 2
Revisions (0)
No revisions yet.