Find the number of all possible combinations with conflicts
I am trying to solve an optimization problem, but first I need to find the number of all possible combinations of n elements, but with some conflicts in mind. A possible example would be:
: {1,2,3,4} conflicts: {1,2}, {3,4}
The term "conflict" means that numbers belonging to the same set of conflicts should not be allocated in the same combination. Also, the sets of conflicts do not always intersect, and there are always two elements in each conflict.
So far I have only found how to calculate all possible combinations, i.e. 2 ^ n.
Thank.
source to share
Conflict sets can be modeled as edges in a graph. You are asking for the number of independent sets of vertices in a graph
An independent vertex set of a graph G is a subset of vertices such that no two vertices in the subset represent an edge of G - http://mathworld.wolfram.com/IndependentVertexSet.html
The above link also refers to what is called an independence polynomial that can be used to count things like this, although this is only useful if the conflict graph is well structured. The general problem of determining the number of independent sets is known to be # P-complete (see https://en.wikipedia.org/wiki/Sharp-P-complete for a definition of this complexity class) so there is little chance that your question will be simple answer. In some cases, Markov chain techniques were used to approximate this number. See http://www.researchgate.net/publication/221590282_Approximately_Counting_Up_To_Four_(Extended_Abstract)
source to share