find the number of all possible combinations with conflicts

Question

I am trying to solve an optimization problem, but first I have to find the number of all possible combinations of n elements but considering some conflicts. A possible example could be:

elements: {1,2,3,4} conflicts: {1,2},{3,4}

The term "conflict" means that the numbers that belong to the same conflict set must not be allocated into the same combination. Also the conflict sets are not always disjoint and the elements in each conflict set are always two.

Until now I only found how all possible combinations can be calculated, that is 2^n.

Thank you.

Answer 1

The conflict sets can be modeled as edges in a graph. You are asking for the number of independent vertex sets in a graph

An independent vertex set of a graph G is a subset of the 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 something called the independence polynomial which can be used to count such things -- though this is useful only if the conflict graph has a nice structure. 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 has a simple answer. Markov-chain techniques have been applied to approximate this number in some cases. See http://www.researchgate.net/publication/221590282_Approximately_Counting_Up_To_Four_(Extended_Abstract)